迷宫连通性判断
时间限制: 3 Sec 内存限制: 128 MB难度：Easy
题目描述
小明最近沉迷于一个游戏，但是他在玩游戏中经常遇到各种各样的迷宫，其中既有走得通的迷宫也有走不通的迷宫。
小明懒得费这个力，想让你帮忙写一个程序帮他一劳永逸地解出所有的迷宫。
输入
第一行输入一个正整数n，代表待求解的迷宫的数量。
其后n组数据，每组数据输入一个数m，代表迷宫的长度和宽度。
其后输入m行，m列的一个矩阵，其中0代表此格有障碍，不能通行，1代表可以通过。
数据保证最左上角和最右下角的格子不会有障碍。
迷宫不会大于30x30。
输出
判断每个迷宫是否能从左上角的起点走到右下角的终点，每个迷宫输出“YES”或“NO”代表这个迷宫是否可以走通。
样例输入
2
3
1 1 0
0 1 1
0 0 1
4
1 1 0 1
0 0 1 1
1 1 0 1
1 1 0 1样例输出
YES
NO提示
使用C++语言解决问题，比Java、JS快数倍。
来源
基础题-模拟类问题
分析
这道题是初级迷宫问题，只要求连通性，不需要求最短路径，还是比较简单的，解题方法是穷举法：穷尽每一条路，直到终点为止。但走过的路就不必再走一遍了，所以走过的地方就变成了路障：我们用bool矩阵存储所有的格子，0表示路障，1表示还未走过的地方，我们递归的目的就是让所有走过的1变成0，途中遇到终点则提前结束。每次递归向上下左右4个方向尝试着走一格，每走一步都要进行以下4个判断：
- 是否有路障？结束函数
- 是否走过了？结束函数
- 是否越界？结束函数
- 到达终点了嘛？结束程序
其中前两种判断我们优化成一种了，剩下3个判断，如果通过了这3个判断，则成功地走到了这个格子，然后这个格子置0，接着再向四个方向走。然后有2种情况：要么走完了所有格子，则走不通，要么中间遇到终点，走通了。
提前结束递归
遇到终点则可以结束程序输出“YES”了，但怎么结束呢？当然可以调用方法结束进程，但如果后面还有活要做，则需要结束当前的递归栈，也就是第一次调用递归函数的地方，return只能结束当前函数，但当前函数已经是递归的第n层栈了，下面还有好多父函数，如何直接结束至栈底呢？思来想去C++里只有throw能实现这个功能，同时还要在栈底进行捕获，似乎JavaScript也只能抛出异常：https://stackoverflow.com/a/13637203/8047150
优先向终点方向走
题目中，终点在右下角，为了更快地到达终点，每次的4次递归优先走右下，再走左上，这样到达终点的时间更短一些。品尝下面的代码：
代码
#include <iostream>
using namespace std;
// 迷宫边长
int n;
bool map[30][30] = {0};
int go(int x, int y){
// 不可走？
if (map[x][y] == false)
return 0;
// 是否越界
if (x < 0 || y < 0 || x >= n || y >= n)
return 0;
// 到达终点？
if (x == n - 1 && y == n - 1)
throw " "; // 结束调用栈
// 已走过，置0
map[x][y] = false;
go(x + 1, y); // 下
go(x, y + 1); // 右
go(x - 1, y); // 上
go(x, y - 1); // 左
return 0;
}
int main(){
// 迷宫数量
int k;
cin >> k;
for (int u = 0; u < k; ++u){
cin >> n;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
cin >> map[i][j];
try{
// 从起点开始递归
go(0, 0);
cout << "NO" << endl; // 全走完了，没遇到终点
}
catch (...){
cout << "YES" << endl; // 遇到终点啦
}
}
return 0;
}
/**************************************************************
Problem: 3844
User: jim
Language: C++
Result: 正确
Time:4 ms
Memory:2320 kb
****************************************************************/