首页 > 代码库 > hdu 1728 逃离迷宫
hdu 1728 逃离迷宫
逃离迷宫
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 16049 Accepted Submission(s): 3918
Problem Description
给定一个m × n (m行, n列)的迷宫，迷宫中有两个位置，gloria想从迷宫的一个位置走到另外一个位置，当然迷宫中有些地方是空地，gloria可以穿越，有些地方是障碍，她必须绕行，从迷宫的一个位置，只能走到与它相邻的4个位置中,当然在行走过程中，gloria不能走到迷宫外面去。令人头痛的是，gloria是个没什么方向感的人，因此，她在行走过程中，不能转太多弯了，否则她会晕倒的。我们假定给定的两个位置都是空地，初始时，gloria所面向的方向未定，她可以选择4个方向的任何一个出发，而不算成一次转弯。gloria能从一个位置走到另外一个位置吗？
Input
第1行为一个整数t (1 ≤ t ≤ 100),表示测试数据的个数，接下来为t组测试数据，每组测试数据中，
第1行为两个整数m, n (1 ≤ m, n ≤ 100),分别表示迷宫的行数和列数，接下来m行，每行包括n个字符，其中字符‘.‘表示该位置为空地，字符‘*‘表示该位置为障碍，输入数据中只有这两种字符，每组测试数据的最后一行为5个整数k, x1, y1, x2, y2 (1 ≤ k ≤ 10, 1 ≤ x1, x2 ≤ n, 1 ≤ y1, y2 ≤ m),其中k表示gloria最多能转的弯数，(x1, y1), (x2, y2)表示两个位置，其中x1，x2对应列，y1, y2对应行。
第1行为两个整数m, n (1 ≤ m, n ≤ 100),分别表示迷宫的行数和列数，接下来m行，每行包括n个字符，其中字符‘.‘表示该位置为空地，字符‘*‘表示该位置为障碍，输入数据中只有这两种字符，每组测试数据的最后一行为5个整数k, x1, y1, x2, y2 (1 ≤ k ≤ 10, 1 ≤ x1, x2 ≤ n, 1 ≤ y1, y2 ≤ m),其中k表示gloria最多能转的弯数，(x1, y1), (x2, y2)表示两个位置，其中x1，x2对应列，y1, y2对应行。
Output
每组测试数据对应为一行，若gloria能从一个位置走到另外一个位置，输出“yes”，否则输出“no”。
Sample Input
25 5
...**
*.**.
.....
.....
*....
1 1 1 1 3
5 5
...**
*.**.
.....
.....
*....
2 1 1 1 3
Sample Output
no
yes
Source
“网新恩普杯”杭州电子科技大学程序设计邀请赛
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstdlib> 5 #include<cstring> 6 #include<queue> 7 using namespace std; 8 char map[105][105]; 9 int vis[105][105];10 int m,n,k,xi,xj,yi,yj,flag;11 int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};12 struct ln{13 int x;14 int y;15 int step;16 }abc,q;17 18 int border(int x,int y)19 {20 if((x>=1&&x<=m) && (y>=1&&y<=n) &&(map[x][y]!=‘*‘) )21 return 1;22 return 0;23 }24 25 void bfs()26 {27 int i;28 queue<struct ln>p;29 abc.x=xi;30 abc.y=xj;31 abc.step=-1;32 vis[abc.x][abc.y]=1;33 34 p.push(abc);35 while(!p.empty())36 {37 abc=p.front();38 p.pop();39 if( (abc.x==yi) &&(abc.y==yj) &&(abc.step<=k) )40 {41 flag=1;42 return ;43 }44 q.step=abc.step+1;//每次的重新读入，证明之前的点4个方向已经45 //全部走完，step+1是从指现在这个点开始生成46 for(i=0;i<4;i++) //的点和方向都是与之前不同的了,使用vis避免47 { //重走48 q.x=abc.x+dir[i][0];49 q.y=abc.y+dir[i][1];50 while(border(q.x,q.y))51 {52 if(!vis[q.x][q.y])//转弯后要避开之前所有点走过的地方53 {54 vis[q.x][q.y]=1;55 p.push(q);56 }57 q.x+=dir[i][0];58 q.y+=dir[i][1];59 }60 }61 }62 return ;63 }64 65 int main()66 {67 int t;68 scanf("%d",&t);69 while(t--)70 {71 memset(map,0,sizeof(map));72 memset(vis,0,sizeof(vis));73 scanf("%d%d",&m,&n);74 for(int i=1;i<=m;i++)75 {76 getchar();77 for(int j=1;j<=n;j++)78 {79 scanf("%c",&map[i][j]);80 }81 }82 scanf("%d%d%d%d%d",&k,&xj,&xi,&yj,&yi);83 flag=0;84 bfs();85 if(flag==1)86 printf("yes\n");87 else88 printf("no\n");89 }90 return 0;91 }
hdu 1728 逃离迷宫
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。