算法训练 Lift and Throw (DFS && 位运算)
问题描述
给定一条标有整点(1, 2, 3, …)的射线. 定义两个点之间的距离为其下标之差的绝对值.
Laharl, Etna, Flonne一开始在这条射线上不同的三个点, 他们希望其中某个人能够到达下标最大的点.
每个角色只能进行下面的3种操作, 且每种操作不能每人不能进行超过一次.
1.移动一定的距离
2.把另一个角色高举过头
3.将举在头上的角色扔出一段距离
每个角色有一个movement range参数, 他们只能移动到没有人的位置, 并且起点和终点的距离不超过movement range.
如果角色A和另一个角***距离为1, 并且角***没有被别的角色举起, 那么A就能举起B. 同时, B会移动到A的位置,B原来所占的位置变为没有人的位置. 被举起的角色不能进行任何操作, 举起别人的角色不能移动.同时, 每个角色还有一个throwing range参数, 即他能把举起的角色扔出的最远的距离. 注意, 一个角色只能被扔到没有别的角色占据的位置. 我们认为一个角色举起另一个同样举起一个角色的角色是允许的. 这种情况下会出现3个人在同一个位置的情况. 根据前面的描述, 这种情况下上面的两个角色不能进行任何操作, 而最下面的角色可以同时扔出上面的两个角色. 你的任务是计算这些角色能够到达的位置的最大下标, 即最大的数字x, 使得存在一个角色能够到达x.
输入格式
输入共三行, 分别为Laharl, Etna, Floone的信息.
每一行有且仅有3个整数, 描述对应角色的初始位置, movement range, throwing range.
数据保证3个角色的初始位置两两不相同且所有的数字都在1到10之间.
输出格式
仅有1个整数, 即Laharl, Etna, Flonne之一能到达的最大距离.
样例输入
9 3 3
4 3 1
2 3 3
样例输出
15
样例说明
一开始Laharl在位置9, Etna在位置4, Flonne在位置2.
首先, Laharl移动到6.
然后Flonne移动到位置5并且举起Etna.
Laharl举起Flonne将其扔到位置9.
Flonne把Etna扔到位置12.
Etna移动到位置15.
做这道题，我煞费苦心，可是却一无所获，毫无头绪，纠结了许久，只是知道一点——标记，将每个状态都表示出来。起初，关于这个标记，我只想到了一种最直观的方法（一会儿讲技巧——位运算标记法，当然这是我自定义的名字），用多个数组分别标记每个动作的状态。如下：
int initialPlace[4], movement[4], throwing[4], tag[4], tagOne[4], tagTwo[4], tagThree[4], tagFour[4];
// 初始位置 可移动距离 可抛出距离 操作？ 操作一？ 操作二？ 操作三？ 举？
// 1-10 1-10 1-10 ［ 1为可操作，0为不可操作 ］ 0未举，1-3
这种方式既繁琐，又缺乏关联性，做起题来十分乏力。
思考了许久没有结果，最后，还是一位擅长搜索资源的学长帮我找到了一个不错的代码，这个代码极其精妙，再一次印证了一句话，没有做不到的，只有想不到的，当然这个代码我拿到手的时候是个没有注释的代码，我费尽周折才从本质解读了这段代码的算法（众所周知，越是精妙的算法，可读性越差，当然有没有注释也会有很大的差距）。
接下来，就该先分享一下代码了：
#include <stdio.h>
#include <string.h>
#define TRUE 1
#define FALSE 0
#define max(a, b) a > b ? a : b
//定义数组大小为4，从一开始，空出下标为0，方便计算
int x[4]; //三个人的位置
int l[4]; //三个人的机动性（可移动距离）
int t[4]; //三个人的抛的距离
int ans = 0; //经过操作后的最远距离，初始化为0
int w[4]; //初始化为0，0表示可以进行操作，非零表示不可以
int p[4]; //初始化为0，表示a[i]所举起的人
int a[4] = {
3, 3, 3, 3}; //初始化为3，表人的状态，这里a对应的二进制为0011，后三位分别是三个动作：抛出，举起，移动。0（无意义）0（不可抛出）1（未进行举起）1（未进行移动）。这道题中，a只有六个可能值：0(0000)、1(0001)、2(0010)、3(0011)、4(0100)、5(0101)，表示人的六种状态
//bool类型
int near(int s)
{
int i = 1;
for (; i <= 3; i++)
{
if (s == x[i] + 1 || s == x[i] - 1)
{
return TRUE;
}
}
return FALSE;
}
//dfs深度遍历
void dfs(int d)
{
int i = 1, j = 1, e = 0;
//每次都取最远（大）的位置
for (; i <= 3; i++)
{
ans = max(ans, x[i]);
}
for (i = 1; i <= 3; i++)
{
//是否可以进行操作
if (w[i])
{
continue;
}
//a[i] == 1 || a[i] == 3（未进行移动且不可抛出）
if ((a[i] & 1) && !(a[i] & 4))
{
for (j = 1; j <= l[i]; j++) //移动
{
x[i] += j; //a[i]向前移动j
a[i] ^= 1; //已移动
if (near(x[i]) || j == l[i]) //如果a[i]移动后的位置旁边有人或者移动距离达到上限
{
dfs(d + 1);
}
x[i] -= j; //归位
x[i] -= j; //a[i]向后移动j
if (near(x[i]) || j == l[i]) //如果a[i]移动后的位置旁边有人或者移动距离达到上限
{
dfs(d + 1);
}
x[i] += j; //归位
a[i] ^= 1; //还原为未移动
}
}
//a[i] == 2 || a[i] == 3 || a[i] == 5（未进行举起）
if (a[i] & 2)
{
for (j = 1; j <= 3; j++) //举起
{
if (i != j && !w[j] && t[i] > 0) //是否可以进行操作
{
if (x[i] == x[j] + 1 || x[j] == x[i] + 1) //a[i]附近是否有人
{
w[j] = 1; //即将举起（抛出）j，抛出前将j是否可操作标记变更为否
a[i] ^= 2; //已举起
a[i] ^= 4; //可抛出
p[i] = j; //记录a[i]举起（抛出）了j
e = x[j]; //记录a[j]的举起前位置
x[j] = -j; //a[j]（被举起）的位置定为负数，只作用于下一层递归时的取最远位置的循环
dfs(d + 1);
x[j] = e; //归位
w[j] = 0; //还原为可以进行操作
a[i] ^= 2; //还原为未举起
a[i] ^= 4; //还原为不可抛出
}
}
}
}
//a[i] == 4 || a[i] == 5（可抛出）
if (a[i] & 4)
{
for (j = 1; j <= t[i]; j++) //抛出
{
w[p[i]] = 0; //变更a[j]为可操作（以下a[j]指a[i]所举起的人）
a[i] ^= 4; //不可抛出
e = x[p[i]]; //记录a[j]被举起前位置
x[p[i]] = x[i] + j; //抛出a[j]，并更新a[j]位置
if (near(x[p[i]]) || j == t[i]) //如果a[j]被抛出后的位置旁边有人或者抛出距离达到上限
{
dfs(d + 1);
}
x[p[i]] -= j; //归位
x[p[i]] -= j; //a[j]向后抛出j
if (near(x[p[i]]) || j == t[i]) //如果a[j]被抛出后的位置旁边有人或者抛出距离达到上限
{
dfs(d + 1);
}
x[p[i]] = e; //还原a[j]为未举起前的位置
a[i] ^= 4; //还原a[j]为可抛出
w[p[i]] = 1; //还原a[j]为不可操作
}
}
}
return ;
}
int main()
{
int i = 1;
//键入每个人的信息
for (; i <= 3; i++)
{
scanf("%d %d %d", &x[i], &l[i], &t[i]);
}
//深度优先遍历
dfs(1);
//输出最远距离
printf("%d\n", ans);
return 0;
}这里，我要说的有两点，第一：dfs远比我想象中的要灵活的多，如果不是看了这段代码，我真不晓得dfs也可以这样多变，这样灵活。一开始根本就不知道这道题如何去用dfs实现它；第二：那就是位运算标记法。上边我的标记的方法已经说过了有很多缺点，唯一的优点就是容易理解，而现在要说的这种标记方法和我用的第一种方法刚好相反，除了不易理解外，其他各方面都十分优异。这里用a[1]、a[2]、a[3]表示三个人的状态，每个人的状态又分为六种，即：0(0000)，1(0001)，2(0010)，3(0011)，4(0100)，5(0101)。
这里我们对其进行初始化，初始化为3，即0011(转换成二进制后的，因为要用到位运算，所以涉及到二进制)，从这个二进制串中，我们可以解读到我们所需要的信息——标记。0（无实际意义，为了方便看所以加上的0）0（不可抛出，若为1，则可抛出）1（未进行举起，若为0，则已经进行举起）1（未进行移动，若为1，则已经进行移动），这里需要强调，只有最后两位是标记是否进行过，而倒数第三位则是标记是否可以进行抛出，之所以这样标记，是因为抛出和举起是连锁的操作关系，我们可以通过标记是否进行举起来锁定抛出次数，而倒数第三位是否可以抛出则可以告诉我们其是否满足抛出的必要条件——头上有人（这里我们知道，就算没有进行过抛出，我们也不一定可以进行抛出动作，必须头上有人才可以进行抛出动作）。故我们这样来定义一个人的三个操作的状态。
我们在代码实现的过程中可以通过位运算来实现每个操作状态的判断，并且我们还有一个十分重要的标记w[i]，它标记了这个人是否可以进行操作，相当于一个总的标记，表示一个人是否被举起，如果被举起，则不可进行操作，否则可以进行操作。
最后细心的你可能会有些疑惑，为什么这里没有考虑如果一个人移动或者被抛到另一个有人的位置上的情况，那我就要麻烦你和我一起思考了，我们的深度优先遍历的条件是(near(x[i]) || j == l[i]) || (x[i] == x[j] + 1 || x[j] == x[i] + 1)，也就是说，我们举起并抛出的那个人必须是我们相邻的人，而不是重叠的人，那么我们纵使不处理重叠位置的情况，其依然可以不影响到最终的结果，所以我们可以不予考虑，导致画蛇添足。
综上所述，为个人对这道题的DFS算法的解读，十分敬佩能写出这样精妙算法的人和能灵活应用位运算的人。我需要好好学习，争取尽快学习到这些编程的精髓之所在。
OVER！！！
查看3道真题和解析
大疆公司氛围 168人发布