文章作者：姜南(Slyar) 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。
这两天开始捡起算法编程做练习，今天碰到了第一个搜索题目，HDU 1010 – Tempter of the Bone
大意为给定一个N*M的迷宫以及起点和终点，迷宫中有一些障碍无法穿过，问能否不重复也不停留地在刚好一共走T步出迷宫。
很基础的深度优先搜索，不剪枝尝试了DFS也可以过。然后尝试了一下大家都在说的奇偶剪枝技巧，效果显著(如下图)。但是感觉很多人的报告里解释的都不是很清楚，这里我也做个总结好了。
这里说下不剪枝的技巧：为了避免多余的边界控制，可以从i=1,j=1开始读迷宫，在读之前将迷宫初始化为全部’X’，即都为墙。这样在迷宫读取完毕后，周围就会自动出现一圈’X’，这样就可以在搜索的时候只判断遇到’X’就return了。
这里贴一下深搜代码，不管剪不剪枝，这一段是可以不用修改的。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
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函数代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
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)算法的奇偶剪枝技巧
