"
-->迷宫
Descriptions:
一天Extense在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n * n的格点组成，每个格点只有2种状态，.和#，前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时，他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Extense想要从点A走到点B，问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#)，则看成无法办到。
Input
第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开始计数的。
Output
k行，每行输出对应一个输入。能办到则输出“YES”，否则输出“NO”。
Sample Input
2
3
.##
..#
#..
0 0 2 2
5
.....
###.#
..#..
###..
...#.
0 0 4 0
Sample Output
YES
NO
题目链接：
https://vjudge.net/problem/OpenJ_Bailian-2790
经典入门级bfs 迷宫搜索题 先简单判断一下初始位置和结束位置 在进行bfs即可
AC代码
#include
#include
#include
#include
#include
#include
#include
#include
#include [span style=""color: rgba(0//代码效果参考：https://v.youku.com/v_show/id_XNjQwMDQxMTcwNA==.html
, 0, 255, 1)"">string#include
#include
#include
#include [span style=""color: rgba(0, 0, 255, 1)"">set
#include
#define mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
using namespace std;
int T,n,m;
int sx,sy,ex,ey;//初始位置 结束位置
char mp【1005】【1005】;//原始地图
int dt【】【2】= { {1,0},{-1,0},{0,1},{0,-1}};//方向
struct node
{
int x,y;//横纵坐标
};
node now,net;
void bfs()
{
int f=0;
queueq;
now.x=sx,now.y=sy;
mp【now.x】【now.y】='#';//这里走过 变'.'为'#'即可
q.push(now);
while(!q.empty())
{
now=q.front();
q.pop();
if(now.x==ex&&now.y==ey)//到达终点
{
f=1;
cout[""YES""[endl;
break;
}
for(int i=0; i[span style=""color: rgba(128, 0, 128, 1)"">4; i++)
{
net.x=now.x+dt【i】【0】;
net.y=now.y+dt【i】【1】;
if(net.x>=0&&net.x=0&&net.y
{
q.push(net);
mp【net.x】【net.y】='#';//这里走过 变'.'为'#'即可
}
}
}
if(f==0)
{
cout[""NO""[endl;
return;
}
}
int main()
{
cinT;
while(T--)
{
cinn;
for(int i=0; i
for(int j=0; j
cinmp【i】【j】;
cinsx]sy]ex]ey;
// cout[mp【sx】【sy】["" ""[mp【ex】【ey】[endl;
if(mp【sx】【sy】=='#'||mp【ex】【ey】=='#')//判断初始与结束位置
cout[""NO""[endl;
else
bfs();//代码效果参考：https://v.youku.com/v_show/id_XNjQwNjg2ODAwNA==.html
}
}
"
