首页 > 代码库 > POJ_1376_bfs
POJ_1376_bfs
题目描述：
给定一个黑白格子的图，黑格子是障碍物，一个线段交点的起点，一个线段交点的终点和初始方向，机器人从起点开始，只能沿着线段，走到终点，期间不能沿着障碍物边缘和墙边缘。
一次操作可以向当前方向走1-3步或者向左右转身，求最小步数。
思路：
由于格子和机器人的线路形式不一样，直接把障碍物转化成不能走的线路，刚开始想dfs，后来发现没法做，只能bfs（凭自己的水平- _ -），记录每次的坐标、方向和操作次数，每个坐标第一次到达的时候必然是次数最少的。另外要注意的是，转头只能左右转，不能向后转，前进的的时候，若当前前进的步数会遇到障碍物，则比这个步数大的步数也必然会遇到障碍物。
一开始提交的时候，以为可以经过边界，一时WA，然后参考了网上代码之后，修改了这个细节就AC了= =。
#include<cstdio>#include<iostream>#include<queue>#include<cstring>using namespace std;int a[55][55],vis[55][55][4],move[][2]= {{-1,0},{0,-1},{1,0},{0,1}};struct robot{ int x,y,dir,num;}start,stop;int main(){ int n,m; char s[10]; while(~scanf("%d%d",&n,&m) && n &&m) { memset(a,0,sizeof(a)); memset(vis,0,sizeof(vis)); int ans = -1; for(int i = 1;i <= n;i++) { for(int j = 1;j <= m;j++) { int temp; scanf("%d",&temp); if(temp) { a[i][j] = 1; a[i+1][j] = 1; a[i][j+1] = 1; a[i+1][j+1] = 1; } } } n++; m++; scanf("%d%d%d%d%s",&start.x,&start.y,&stop.x,&stop.y,s); start.x++; start.y++; stop.x++; stop.y++; switch(s[0]) { case ‘n‘: start.dir = 0;break; case ‘s‘: start.dir = 2;break; case ‘w‘: start.dir = 1;break; case ‘e‘: start.dir = 3;break; } queue<robot> q; start.num = 0; q.push(start); while(!q.empty()) { robot now = q.front(); q.pop(); int xx = now.x,yy = now.y,dirr = now.dir,numm = now.num; if(xx == stop.x && yy == stop.y) { ans = numm; printf("%d\n",ans); break; } if(xx <= 1 || xx >= n || yy <= 1 || yy >= m || vis[xx][yy][dirr] || a[xx][yy]) { continue; } for(int i =0;i <= 3;i++) { if(i-dirr ==0 || i-dirr == 2 || i- dirr ==-2) { continue; } else { robot temp; temp.x = xx; temp.y = yy; temp.dir = i; temp.num = numm+1; q.push(temp); } } for(int i = 1;i <= 3;i++) { int xxx = xx+move[dirr][0]*i,yyy = yy+move[dirr][1]*i; if (a[xxx][yyy] == 1) { break; } robot temp; temp.x = xxx; temp.y = yyy; temp.dir = dirr; temp.num = numm+1; q.push(temp); } vis[xx][yy][dirr] = 1; } if(ans == -1) printf("-1\n"); } return 0;}
POJ_1376_bfs
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。