MYOJ_4204:迷宫(图论-网格图基础，dfs,bfs在网格图中应用)
题目描述
一天 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
思路：
有概念还是很容易炫的(我指的是dfs)，但是bfs就不是那么好写
先讲简单的~~~
方法1：dfs
STEP 1:定义方向数组，顺序无所谓，99%的网格图都会用到这个；m用于存储网格图上每个字符；vis记录是否被访问。(P.S.以后的网格图若没有特殊说明都是要用到这个的，以后就不说了~~~)
STEP 2:dfs，先把传进来的地址标记为访问过，然后遍历方向数组的四个方向，计算下一个格子坐标，如果满足下一个格子是否在网格范围内、未被访问过且可以通过，就递归继续以此点搜索。
STEP 3:输入测试样例数，读取网格大小及内容。
STEP 4:由于dfs需要，输入起点和终点的坐标后，需要将坐标全部加1，否则over
STEP 5:从起点开始DFS，完成后根据重点是否被访问，输出YES或NO
#include<bits/stdc++.h>
using namespace std;
int k,n,xa,ya,xb,yb,dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};
char m[101][101];
bool vis[101][101];
void dfs(int sx,int sy)
{
vis[sx][sy]=true;
for(int i=0;i<4;i++)
{
int x=sx+dir[i][0],y=sy+dir[i][1];
if(x>=1&&x<=n&&y>=1&&y<=n&&!vis[x][y]&&m[x][y]=='.')
{
dfs(x,y);
}
}
}
int main()
{
scanf("%d",&k);
while(k--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>m[i][j];
}
}
scanf("%d%d%d%d",&xa,&ya,&xb,&yb);
xa++,xb++,ya++,yb++;
memset(vis,0,sizeof(vis));
dfs(xa,ya);
cout<<(vis[xb][yb]==true?"YES\n":"NO\n");
}
}
方法2：bfs
这个难一点，不过高手在民间，在座各位应该都能炫吧~
STEP 1:定义node结构体在bfs使用
STEP 2:bfs,先定义一个队列，用于存储待访问的格子，然后标记起点为已访问并加入队列，当队列不为空时，搜索：搜索时取出队列中的第一个格子并从队列中移除，遍历四个方向，计算下一个格子的坐标，检查这个格子是否在网格范围内、未被访问过且可以通过，如果都满足，就标记该格子为已访问并加入队列
下面和dfs一样，把函数名改了就行
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int x,y;
};
int n,k,xa,ya,xb,yb,dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};
char m[101][101];
bool vis[101][101];
void bfs(int stx,int sty)
{
queue<Node>q;
vis[stx][sty]=true;
q.push(Node{stx,sty});
while(!q.empty())
{
int sx=q.front().x,sy=q.front().y;
q.pop();
for(int i=0;i<4;i++)
{
int x=sx+dir[i][0],y=sy+dir[i][1];
if(x>=1&&x<=n&&y>=1&&y<=n&&!vis[x][y]&&m[x][y]=='.')
{
vis[x][y]=true;
q.push(Node{x,y});
}
}
}
}
int main()
{
scanf("%d",&k);
while(k--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>m[i][j];
}
}
scanf("%d%d%d%d",&xa,&ya,&xb,&yb);
xa++,xb++,ya++,yb++;
memset(vis,0,sizeof(vis));
bfs(xa,ya);
cout<<(vis[xb][yb]==true?"YES\n":"NO\n");
}
}