首页 > 代码库 > openjudge 1792 迷宫 解析报告
openjudge 1792 迷宫 解析报告
关于一道大水题的解析报告。
1792:迷宫
总时间限制: 3000ms 内存限制: 65536kB
描述
一天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嘛。广搜对于这种最短路径就是最好的方法。
更何况，这道题就是问你这个能不能走过，而不是问最短路径。所以就变的更简单了。
简单来说，就是套路。
队列，BFS，状态。
嗯就是这样。
hhh这道水题是我用vim第一次AC的题。
等用过Vim，就会突然觉得。这种不用鼠标的感觉，只依赖双手的打字速度的工具简直，就是完美。
1 #include<cstdio> 2 #include<string.h> 3 using namespace std; 4 char map_1[101][101]; 5 int x1,y1,x2,y2; 6 struct node { 7 int x,y; 8 }; 9 int map_2[101][101];10 int x_1[5]={0,1,-1,0,0};11 int x_2[5]={0,0,0,1,-1};12 node q[100001];13 int heads,lose;14 void push(node a)15 {16 q[++lose]=a;17 return ;18 }19 int BFS()20 {21 node a;22 a.x=x1;a.y=y1;23 q[1]=a;24 while(heads<=lose)//队列里有没有东西。查看状态有没有全部枚举完25 {26 node n;27 n=q[heads];28 heads++;29 if(n.x==x2&&n.y==y2){//发现诶！可以！30 printf("YES\n");31 return 0;32 }33 for(int i=1;i<=4;i++)34 {35 node n1;36 n1=n;37 if(!map_2[n1.x+x_1[i]][n1.y+x_2[i]]&&map_1[n1.x+x_1[i]][n1.y+x_2[i]]==‘.‘)//判断继续能不能走38 {39 n1.x+=x_1[i];40 n1.y+=x_2[i];41 push(n1);42 map_2[n1.x][n1.y]=1;43 }44 }45 }46 printf("NO\n");47 return 0;48 }49 int main()50 {51 int n,m;52 scanf("%d",&n);53 while(n--)54 {55 memset(map_1,‘#‘,sizeof(map_1));56 memset(map_2,0,sizeof(map_2));//初始化。这个一定不要忘了。57 heads=lose=1;58 scanf("%d\n",&m);59 for(int i=1;i<=m;i++)60 {61 for(int j=1;j<=m;j++)62 {63 scanf("%c",&map_1[i][j]);64 }65 scanf("\n");66 }67 scanf("%d%d%d%d",&x1,&y1,&x2,&y2);68 x1+=1;y1+=1;x2+=1;y2+=1;//这道题这个地方特别坑，认真读题69 if(map_1[x1][y1]==‘#‘||map_1[x2][y2]==‘#‘)70 {71 printf("NO\n");72 continue;73 }74 BFS();75 }76 return 0;77 }
嗯就是这样。
openjudge 1792 迷宫 解析报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。