本文主要是介绍Poj 2049 Finding Nemo(建图+BFS)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
先把DP放一放，开始刷Poj上的图论。从基础走起。。
http://poj.org/problem?id=2049
题意：给一个map,它包含墙，门及空地。输入n，m分别代表墙的个数及门的个数。
对于墙，输入x,y,d,t,（x,y）是墙的左下角的坐标；d = 1平行y轴，d=0平行x轴；t代表墙延伸的长度。
对于门，输入x,y,d,(x,y)是门的左下角坐标，d同上，因为门的长度始终为1，t即忽略.
最后给出Nemo的坐标，保证他在空地上。
Nemo的爸爸在（0,0）点，问他救到Nemo经过的最少的门，若救不到输出-1。
思路：BFS。但按题目中的map，不好建图表示各个点的坐标，所以每一条边用三个点表示，左端点，右端点及中间点。相当于把图扩大2倍。用1表示墙，0表示空地，2表示门。
还有注意的就是map的坐标范围是[1,199]，所以如果Nemo的坐标不在该范围内，直接输出0，因为没必要经过门。
BFS的时候不能超出边界，可以在Nemo的爸爸范围之外加上一道墙。
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;int dir[4][2] = { {0,-1},{0,1},{-1,0},{1,0} };struct node
{int x,y;int step;bool operator < (const struct node &tmp)const{return step > tmp.step;}
};int map[410][410];
int ex,ey;
int vis[410][410];
priority_queue <struct node> que;int bfs()
{memset(vis,0,sizeof(vis));while(!que.empty()) que.pop();vis[1][1] = 1;que.push((struct node){1,1,0});while(!que.empty()){struct node u = que.top();que.pop();if(u.x == ex && u.y == ey){return u.step;}for(int d = 0; d < 4; d++){int x = u.x+dir[d][0];int y = u.y+dir[d][1];if(map[x][y] != 1 && !vis[x][y]){vis[x][y] = 1;if(map[x][y] == 0)que.push((struct node) {x,y,u.step});else que.push((struct node) {x,y,u.step+1});}}}return -1;
}int main()
{int n,m;while(~scanf("%d %d",&n,&m)){if(n == -1 && m == -1) break;int x,y,d,t;memset(map,0,sizeof(map));//建图while(n--){scanf("%d %d %d %d",&x,&y,&d,&t);if(d == 1){for(int i = y*2; i <= (y+t)*2; i++)map[x*2][i] = 1;}else{for(int i = x*2; i <= (x+t)*2; i++)map[i][y*2] = 1;}}while(m--){scanf("%d %d %d",&x,&y,&d);if(d == 1)map[2*x][2*y+1] = 2;else map[2*x+1][2*y] = 2;}double e_x,e_y;scanf("%lf %lf",&e_x,&e_y);if(e_x < 0 || e_x > 199 || e_y < 0 || e_y > 199)//终点原本就不再sea内，就没必要经过门{printf("0\n");continue;}ex = (int)e_x*2+1;ey = (int)e_y*2+1;for(int i = 0; i <= 400; i++) //周围加一道墙map[i][0] = map[i][400] = map[0][i] = map[400][i] = 1;int ans = bfs();printf("%d\n",ans);}return 0;
}
这篇关于Poj 2049 Finding Nemo(建图+BFS)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
