首页 > 代码库 > nefu558 bfs
nefu558 bfs
Description
AC小公主很喜欢设计迷宫，她设计的迷宫只有两个口，一个入口，一个出口。但小公主有时候很调皮，她会让挑战者走不出迷宫。现在给你AC小公主的迷宫请你判断挑战者能否成功从出口走出迷宫，迷宫包证边界为障碍物，只有两个不同的入口。“#”代表障碍物，“*”代表可走的路。
Input
输入有多组，每组输入两个正整数n，m（ 2 < n < m < 1000）。接下来n行，每行有m个字符。
Output
每组测试实例，若挑战者能走出迷宫输出”YES”，否则输出“NO”。
Sample Input
3 3#*##*##*#3 3#*#####*#
Sample Output
YESNO
AC代码：
#include<cstdio>#include<cstring>#include<queue>using namespace std;char str[1005][1005];bool flag[1005][1005];int dri[4][2]= {{-1,0},{1,0},{0,-1},{0,1}};struct Door{ int x,y;} door[2];int bfs(int n,int m){ memset(flag,false,sizeof(flag)); queue<Door>q; Door now,next; q.push(door[0]); flag[door[0].x][door[0].y]=true; while(!q.empty()) { now=q.front(); q.pop(); if(now.x==door[1].x && now.y==door[1].y) return 1; for(int i=0; i<4; i++) { next.x=now.x+dri[i][0]; next.y=now.y+dri[i][1]; if(next.x>=0&&next.x<n && next.y>=0&&next.y<m && next.x==door[1].x && next.y==door[1].y) return 1; else if(next.x>=0&&next.x<n && next.y>=0&&next.y<m && !flag[next.x][next.y] && str[next.x][next.y]==‘*‘) { q.push(next); flag[next.x][next.y]=true; } } } return -1;}int main(){ int n,m,i; while(scanf("%d%d",&n,&m)==2) { getchar(); for(i=0; i<n; i++) scanf("%s",str[i]); int num=0; for(i=0; i<m; i++) { if(str[0][i]==‘*‘) { door[num].x=0; door[num].y=i; num++; } if(str[n-1][i]==‘*‘) { door[num].x=n-1; door[num].y=i; num++; } } for(i=1; i<n-1; i++) { if(str[i][0]==‘*‘) { door[num].x=i; door[num].y=0; num++; } if(str[i][m-1]==‘*‘) { door[num].x=i; door[num].y=m-1; num++; } } int ans=bfs(n,m); if(ans==1) printf("YES\n"); if(ans==-1) printf("NO\n"); } return 0;}
nefu558 bfs
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。