文章作者：姜南(Slyar) 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。
这两天开始捡起算法编程做练习，今天碰到了第一个搜索题目，HDU 1010 – Tempter of the Bone
大意为给定一个N*M的迷宫以及起点和终点，迷宫中有一些障碍无法穿过，问能否不重复也不停留地在刚好一共走T步出迷宫。
很基础的深度优先搜索，不剪枝尝试了DFS也可以过。然后尝试了一下大家都在说的奇偶剪枝技巧，效果显著(如下图)。但是感觉很多人的报告里解释的都不是很清楚，这里我也做个总结好了。
这里说下不剪枝的技巧：为了避免多余的边界控制，可以从i=1,j=1开始读迷宫，在读之前将迷宫初始化为全部’X’，即都为墙。这样在迷宫读取完毕后，周围就会自动出现一圈’X’，这样就可以在搜索的时候只判断遇到’X’就return了。
这里贴一下深搜代码，不管剪不剪枝，这一段是可以不用修改的。
int dfs(int x, int y, int T)
{
// 碰到X即为边界返回
if (map[x][y] != '.' && map[x][y] != 'S') return 0;
// 剩一步时即可判断是否为出口，找到返回1
if (T == 1)
{
if (map[x-1][y] == 'D') return 1;
if (map[x+1][y] == 'D') return 1;
if (map[x][y-1] == 'D') return 1;
if (map[x][y+1] == 'D') return 1;
return 0;
}
else
{
// 标记走过
map[x][y] = 'X';
// 深度优先搜索
if (map[x-1][y] == '.' && dfs(x-1, y, T-1)) return 1;
if (map[x+1][y] == '.' && dfs(x+1, y, T-1)) return 1;
if (map[x][y-1] == '.' && dfs(x, y-1, T-1)) return 1;
if (map[x][y+1] == '.' && dfs(x, y+1, T-1)) return 1;
// 还原走过
map[x][y] = '.';
return 0;
}
return 0;
}
关于奇偶剪枝
首先举个例子，有如下4*4的迷宫，’.’为可走路段，’X’为障碍不可通过
S...
....
....
...D
从S到D的最短距离为两点横坐标差的绝对值+两点纵坐标差的绝对值 = abs(Sx – Dx) + abs(Sy – Dy) = 6，这个应该是显而易见的。
遇到有障碍的时候呢
S.XX
X.XX
...X
...D
你会发现不管你怎么绕路，最后从S到达D的距离都是最短距离+一个偶数，这个是可以证明的
而我们知道：
奇数 + 偶数 = 奇数
偶数 + 偶数 = 偶数
因此不管有多少障碍，不管绕多少路，只要能到达目的地，走过的距离必然是跟最短距离的奇偶性是一致的。
所以如果我们知道从S到D的最短距离为奇数，那么当且仅当给定的步数T为奇数时，才有可能走到。如果给定的T的奇偶性与最短距离的奇偶性不一致，那么我们就可以直接判定这条路线永远不可达了。
这里还有个小技巧，我们可以使用按位与运算来简化奇偶性的判断。我们知道1的二进制是1，而奇数的二进制最后一位一定是1，而偶数的二进制最后一位一定是0。所以如果数字&1的结果为1，那么数字为奇数，反之为偶数。
下面给出奇偶剪枝后的main函数代码
int main()
{
int sx, sy, ex, ey;
int N, M, T, i, j;
while(1)
{
scanf("%d %d %d", &N, &M, &T);
getchar();
if (N == 0) break;
// 把周围边界全部变成X
memset(map,'X',sizeof(map));
// 从1开始读，留出边界位置
for (i = 1; i <= N; i++)
{
for (j = 1; j <= M; j++)
{
scanf("%c", &map[i][j]);
if (map[i][j] == 'S')
{
sx = i;
sy = j;
}
else if (map[i][j] == 'D')
{
ex = i;
ey = j;
}
}
getchar();
}
// 奇偶剪枝，对1用按位与运算求奇偶
if ((abs(ex - sx) + abs(ey - sy) - T)&1)
{
printf("NO\n");
}
else if (dfs(sx, sy, T) == 1)
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
return 0;
}
转载请注明：Slyar Home » 总结深度优先搜索(DFS)算法的奇偶剪枝技巧
