这是一道OJ题引发的博文和现实的技巧……(不是来看题的同学就翻到最后吧)
PART I - 上来就扔题 （掀桌
摸墙算法（SZUOJ Problem 1402）
Description
给出一个n*n的迷宫矩阵示意图，从起点[0,0]出发，寻找路径到达终点[n-1, n-1]。
本题使用摸墙算法走迷宫。摸墙走算法也称绕墙走算法，是一种运用左手/右手法则进行迷宫搜索的初级算法。
如果迷宫是简单连通的，即迷宫的墙总是相互相连的或与迷宫的外轮廓相连，那么迷宫的搜索者从起点开始将一只手扶在墙面前行，总能保证不会迷失并且找到迷宫中存在的出口。
现假设使用左手法则饶墙走迷宫，即左手不离墙。且假设总能走到出口。输出从起点到终点的路径。
Input
第一行输入t，表示有t个迷宫
第二行输入n，表示第一个迷宫有n行n列
第三行起，输入迷宫每一行的每个方格的状态，0表示可通过，1表示不可通过
以此类推输入下一个迷宫
Output
对每个迷宫，输出从起点 [0,0] 到终点[n-1,n-1] 的路径。
Sample Iutput
2
4
0 1 1 0
0 1 1 1
0 0 0 1
0 0 0 0
8
0 0 0 1 1 1 1 1
1 0 0 0 1 0 0 1
1 0 0 0 1 0 0 0
1 1 0 0 0 0 0 1
0 0 1 1 0 1 1 0
0 0 0 0 0 0 1 1
1 1 1 1 1 0 0 1
0 0 0 0 1 0 0 0
Sample Output
[0,0]–[1,0]–[2,0]–[2,1]–[2,2]–
[3,2]–[3,3]
[0,0]–[0,1]–[0,2]–[1,2]–[1,3]–
[2,3]–[3,3]–[3,4]–[3,5]–[2,5]–
[1,5]–[1,6]–[2,6]–[2,7]–[2,6]–
[3,6]–[3,5]–[3,4]–[4,4]–[5,4]–
[5,5]–[6,5]–[6,6]–[7,6]–[7,7]
▲ 思路
- 如何知道上下左右？
走路的时候不可避免需要知道左右和前面的方向向量，可是人的方向不同，他对应的左右和前面的方向向量也就不同。一开始我在想的时候是，先确定自身走路的方向，再分别讨论各个方向对应的前面和左右，但是这样打出来的代码会非常非常长长长长长~~~，那么如果我以一定方向定义方向向量数组，能否通过当前方向与前面、左右的相互联系获得他们的方向向量？答案是可以的。
如图，我以逆时针方向定义方向向量数组上右下左 dir[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} }，而我当前方向则用dir_current(dir_current = 0, 1, 2, 3)表示，那么前面的方向向量则为对应自身方向dir[dir_current][2]，左边的方向则对应dir[(dir_current - 1 + 4)%4][2]（加上4是加上一个周期的意思，防止0-1=-1的情况出现），右边的方向对应dir[(dir_current + 1)%4][2]
现在有了方向向量数组，就能得到前面的坐标为forward_x = loc_x + dir[dir_current][0],forward_y = loc_y + dir[dir_current][1]， 左边的坐标为left_x = loc_x + dir[(dir_current -1 + 4)%4][0],left_y = loc_y + dir[(dir_current -1 + 4)%4][1]。 - 如何走路？
摸墙算法走迷宫可以分为三种情况：
① 左边有墙，前面有墙
因为左手法则要求左手要时刻贴墙，因此此时需要在原地右转，即dir_current = (dir_current + 1)%4。
② 左边没墙
首先应该确定的是，左边没墙一定是从左边有墙那里走过来的，因为摸墙算法要求人的手时刻贴墙。那么人从左边有墙走到左边没墙，只可能发生在拐角处，此时应该原地左转，即dir_current = (dir_current - 1 + 4)%4
③ 前面没墙
除了在拐角处，人的左手一定靠墙，即左边一定有墙，此时应该往前走；而人在拐角处原地左拐后也应该往前走。
因此，如果前面没墙，在判定并执行前两种情况后，只需要往前走就可以了，即loc_x += dir[dir_current][0],loc_y += dir[dir_current][1]。
记得每次左转右转或者前进的时候都应该更新前面的坐标left_x,left_y和forward_x,forward_y。
▲ 代码
//摸墙算法
#include <bits/stdc++.h>
using namespace std;
const int dir[4][2] = { {-1, 0}, {0, 1}, {1, 0}, {0, -1} };
bool is_in_border(int x, int y, int size){
if(x >= 0 && x <= size - 1 && y >= 0 && y <= size - 1){
return true;
}else{
return false;
}
}
void change_dir(int loc_x, int loc_y, int& left_x, int& left_y, int& forward_x, int& forward_y, int& dir_current, int change){
dir_current = (dir_current + change + 4)%4;
left_x = loc_x + dir[(dir_current + 3)%4][0];
left_y = loc_y + dir[(dir_current + 3)%4][1];
forward_x = loc_x + dir[dir_current%4][0];
forward_y = loc_y + dir[dir_current%4][1];
}
int main()
{
int t;
cin >> t;
while(t--){
int dir_current = 0;
int array[100][100];
int size;
int loc_x = 0, loc_y = 0, left_x, left_y, forward_x, forward_y;
int count = 1;
cin >> size;
for(int i = 0; i <= size - 1; i++){
for(int j = 0; j <= size - 1; j++){
cin >> array[i][j];
}
}
printf("[0,0]");
if(size > 1){
cout << "--";
}
while(1){
change_dir(loc_x, loc_y, left_x, left_y, forward_x, forward_y, dir_current, 0);
if(is_in_border(left_x, left_y, size) && array[left_x][left_y] == 0){
change_dir(loc_x, loc_y, left_x, left_y, forward_x, forward_y, dir_current, -1);
}
if(!is_in_border(forward_x, forward_y, size) || array[forward_x][forward_y] == 1){
change_dir(loc_x, loc_y, left_x, left_y, forward_x, forward_y, dir_current, 1);
}
if(is_in_border(forward_x, forward_y, size) && array[forward_x][forward_y] == 0){
loc_x += dir[dir_current][0];
loc_y += dir[dir_current][1];
printf("[%d,%d]", loc_x, loc_y);
count++;
if(loc_x == size - 1 && loc_y == size - 1){
cout << endl;
break;
}else{
printf("--");
}
if(count%5 == 0){
cout << endl;
}
}
}
}
return 0;
}
PART II - 后言
其实写这篇文章不单单是为了说明这种方向向量数组和当前方向相互联系的思维啦，还有介绍现实中走迷宫方法的意图[手动滑稽]。
现实生活中走迷宫不可能用DFS的，毕竟根本就记不住自己走了哪些地方，更不可能用BFS的，人又不能分身。但是这种摸墙的方法是可以一试的！
