本文主要是介绍POJ 2049 Finding Nemo(三维BFS），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目地址：http://poj.org/problem?id=2049
这题WA了一天啊，结果最后把C++改成G++就过了。。不知道为什么。。
这题思路是把每个网格的坐标用网格左下角坐标来代替，用第三维来代表网格的上边和右边。
然后BFS搜索，要全部搜索完取最小值。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <algorithm>using namespace std;
struct node
{int x, y, ans;
};
int mp[220][220][3], vis[220][220];/*mp数组结果，0代表空地，1代表门，2代表墙，第三维的0代表此表格的上方，1代表表格的右侧*/
int jx[]= {0,0,1,-1};
int jy[]= {1,-1,0,0};
int min1;
void bfs(int s, int t)
{int i, j;queue<node>q;node f1, f2;f1.x=s;f1.y=t;f1.ans=0;vis[s][t]=1;q.push(f1);min1=10000000;while(!q.empty()){f1=q.front();q.pop();//if(f1.x<=4&&f1.y<=4)//printf("%d %d %d\n",f1.x, f1.y, f1.ans);if(f1.x>=199||f1.y>=199||f1.x==0||f1.y==0){if(min1>f1.ans){min1=f1.ans;}continue ;}if(f1.ans>=min1)continue ;f2.x=f1.x+jx[0];f2.y=f1.y+jy[0];if(!vis[f2.x][f2.y]&&mp[f1.x][f1.y][0]!=2)//向下走{if(mp[f1.x][f1.y][0]==1)f2.ans=f1.ans+1;elsef2.ans=f1.ans;vis[f2.x][f2.y]=1;q.push(f2);}f2.x=f1.x+jx[1];f2.y=f1.y+jy[1];if(!vis[f2.x][f2.y]&&mp[f2.x][f2.y][0]!=2)//向下走{if(mp[f2.x][f2.y][0]==1)f2.ans=f1.ans+1;elsef2.ans=f1.ans;vis[f2.x][f2.y]=1;q.push(f2);}f2.x=f1.x+jx[2];f2.y=f1.y+jy[2];if(!vis[f2.x][f2.y]&&mp[f1.x][f1.y][1]!=2)//向右走{if(mp[f1.x][f1.y][1]==1)f2.ans=f1.ans+1;elsef2.ans=f1.ans;vis[f2.x][f2.y]=1;q.push(f2);}f2.x=f1.x+jx[3];f2.y=f1.y+jy[3];if(!vis[f2.x][f2.y]&&mp[f2.x][f2.y][1]!=2)//向左走{if(mp[f2.x][f2.y][1]==1)f2.ans=f1.ans+1;elsef2.ans=f1.ans;vis[f2.x][f2.y]=1;q.push(f2);}}
}
int main()
{int n, m, i, j, a, b, c, d;double x, y;while(scanf("%d%d",&n,&m)!=EOF){if(n==-1&&m==-1) break;memset(mp,0,sizeof(mp));for(i=0; i<n; i++){scanf("%d%d%d%d",&a, &b, &c, &d);if(c){for(j=0; j<d; j++){mp[a-1][b+j][1]=2;//printf("%d %d 0\n",a-1,b+j);}}else{for(j=0; j<d; j++){mp[a+j][b-1][0]=2;//printf("%d %d 1\n",a+j,b-1);}}}for(i=0; i<m; i++){scanf("%d%d%d",&a,&b,&c);if(c){mp[a-1][b][1]=1;}else{mp[a][b-1][0]=1;}}scanf("%lf%lf",&x,&y);a=x;b=y;if(a>=199||b>=199||a<=0||b<=0){printf("0\n");continue ;}memset(vis,0,sizeof(vis));bfs(a,b);if(min1==10000000)printf("-1\n");elseprintf("%d\n",min1);}return 0;
}
这篇关于POJ 2049 Finding Nemo(三维BFS）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
