描述：
一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n * n的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#)，则看成无法办到。
输入：
第1行是测试数据的组数k，后面跟着k组输入。每组测试数据的第1行是一个正整数n (1 <= n <= 100)，表示迷宫的规模是n * n的。接下来是一个n * n的矩阵，矩阵中的元素为.或者#。再接下来一行是4个整数ha, la, hb, lb，描述A处在第ha行, 第la列，B处在第hb行, 第lb列。注意到ha, la, hb, lb全部是从0开始计数的。
输出：
k行，每行输出对应一个输入。能办到则输出“YES”，否则输出“NO”。
样例输入：
2 3 .## ..# #.. 0 0 2 2 5 ..... ###.# ..#.. ###.. ...#. 0 0 4 0
样例输出：
YES NO
思路：
这个题目可以运用深度优先搜索和广度优先搜索去运算。
深度优先搜索时从起点开始搜索，每搜索一个点后应标记一下，当碰到数组越界以及无法行走的点之后应返回上一级，最后通过判断终点是否被标记即可。
广度优先搜索时也是从起点开始出发，每当经过岔路口（即是：可以往多方向行走的路口时）要一分为多，分别走，当某一条路无法行通的时候，就只需保留其点，去进行其他点的判断即可。在广度优先搜索时，我们需要建立一个队列，去存放点，并且当存放下一路口点时，上一点要删除，最终返回的条件则是判断队列中是否为空即可。
代码：
BFS：
#include <iostream> #include <cstring> #include <queue> using namespace std ; char a[100][100] ; int sx, sy, ex, ey, n , t; bool vis[100][100] ; struct node { int x, y ; node(int xx=0, int yy=0) { x = xx ; y = yy ; } }; int dx[] = {0,0,-1,1} ; int dy[] = {-1,1,0,0} ; void bfs() { queue<node> q ; vis[sx][sy] = true ; q.push(node(sx,sy)) ; while(!q.empty()) { node f = q.front() ; q.pop() ; for(int i=0; i<4; i++) { node tmp ; tmp.x = f.x + dx[i] ; tmp.y = f.y + dy[i] ; if(tmp.x>=0 && tmp.x<n && tmp.y>=0 &&tmp.y<n) if(a[tmp.x][tmp.y] == '.') if(vis[tmp.x][tmp.y] == false) { vis[tmp.x][tmp.y] = true ; q.push(tmp) ; } } } } int main() { cin >> t ; while(t--) { cin >> n ; for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { cin >> a[i][j] ; } } cin >> sx >> sy >> ex >> ey ; memset(vis, false, sizeof(vis)) ; if(a[sx][sy] == '#' || a[ex][ey] == '#') cout << "NO" << endl ; else { bfs() ; if(vis[ex][ey] == true) cout << "YES" << endl ; else cout << "NO" << endl ; } } return 0 ; }
DFS：
#include <iostream> #include <cstring> using namespace std ; char a[110][110] ; bool f[110][110] ; int sx, sy, ex, ey, n ,k ; void dfs(int x, int y) { f[x][y] = true ; if(x==ex && y==ey) return ; if(x+1<n && f[x+1][y]==false && a[x+1][y]=='.') dfs(x+1, y) ; if(x-1>=0 && f[x-1][y]==false && a[x+1][y]=='.') dfs(x-1, y) ; if(y+1<n && f[x][y+1]==false && a[x+1][y]=='.') dfs(x, y+1) ; if(y-1>=0 && f[x][y-1]==false && a[x+1][y]=='.') dfs(x, y-1) ; } int main() { cin >> k ; while(k--) { memset(f, false, sizeof(f) ) ; cin >> n ; for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { cin >> a[i][j] ; } } cin >> sx >> sy >> ex >> ey ; if(a[sx][sy] == '#' || a[ex][ey] == '#') { cout << "NO" << endl ; } else { dfs(sx, sy) ; if(f[ex][ey] == true) cout<<"YES" << endl ; else cout << "NO" << endl ; } } return 0 ; }
