題目鏈接：http://poj.org/problem?id=2049

解題報告：

網格中的BFS，最主要的是邊界問題。

1、這里在左右，上下兩個方向上，分別判斷墻，和門，細節是，向上有t個墻，for(int j=0;j<t;j++) ya[x][y+1+j]=WALL; ? ymax=max(y+t+1,ymax);xmax=max(x+1,xmax);

2、這里采用的是逆向BFS，從dis[1][1]出發，輸出dis[tx][ty];

?

#include <iostream> #include <queue> #include <stdio.h> #include <string.h>using namespace std;#define MAXV 210 #define INF 1<<29 #define min(a,b) (a>b?b:a) #define max(a,b) (a>b?a:b)#define EMPTY 0 #define DOOR 1 #define WALL INFint xa[MAXV][MAXV]; ///在x方向上添上墻 int ya[MAXV][MAXV]; ///在y方向上添上墻int dis[MAXV][MAXV]; ///目標答案，dis[i][j]先初始化為無窮，然后置dis[1][1]為0，///根據x,y方向上的是否有墻，自增，沒有墻置+0，有門+1，dis[tx][ty]也就是答案int dt[4][2]= {{-1,0},{1,0},{0,-1},{0,1}}; ///四個方向分別是向上，向下，向左，向右int xmax,ymax; ///x,y方向上的邊界///判斷是否在圖表中 bool pd(int x,int y) {if(x>0 && x<=xmax && y<=ymax && y>0) return 1;return 0; }int getvalue(int x,int y,int i) {if(i==0) return ya[x-1][y];if(i==1) return ya[x][y];if(i==2) return xa[x][y-1];return xa[x][y]; }///逆向廣搜 int bfs(int tx,int ty) {int i,j,vx,vy,dx,dy,tmp;queue <int>q;///初始化for(i=1; i<=ymax; i++){for(j=1; j<=xmax; j++)dis[i][j]=INF;}dis[1][1]=0;q.push(1);q.push(1);while(!q.empty()){vx=q.front();q.pop();vy=q.front();q.pop();for(i=0; i<4; i++){dx=vx+dt[i][0];dy=vy+dt[i][1];tmp=getvalue(vx,vy,i); ///tmp為這個格子是否為墻，門，什么都沒有，分別對應inf,1,0if(pd(dx,dy) && dis[dx][dy]>dis[vx][vy]+tmp){dis[dx][dy]=dis[vx][vy]+tmp;q.push(dx);q.push(dy);}}}return (dis[tx][ty]==INF?-1:dis[tx][ty]); }int main() {int n,m,i,j;int x,y,d,t;double sx,sy;while(scanf("%d%d",&m,&n)){///m個墻，n個門if(m==-1 && n==-1) break;ymax=xmax=-1;memset(xa,EMPTY,sizeof(xa));memset(ya,EMPTY,sizeof(ya));for(i=0; i<m; i++){scanf("%d%d%d%d",&x,&y,&d,&t);if(d) ///向上有墻 {for(j=0; j<t; j++)ya[x][y+j+1]=WALL;ymax=max(y+t+1,ymax);xmax=max(x+1,xmax);}else{for(j=0; j<t; j++)xa[x+j+1][y]=WALL;ymax=max(y+1,ymax);xmax=max(x+t+1,xmax);}}for(i=0; i<n; i++){scanf("%d%d%d",&x,&y,&d);if(d) ya[x][y+1]=DOOR;else xa[x+1][y]=DOOR;}scanf("%lf%lf",&sx,&sy);if(!(sx>=1 && sx<=199 && sy>=1 && sy<=199)) printf("0\n");else printf("%d\n",bfs((int)sx+1,(int)sy+1));}return 0; } View Code

參考：http://blog.csdn.net/wangjian8006/article/details/7997609

轉載于:https://www.cnblogs.com/TreeDream/p/5392655.html

總結

以上是生活随笔為你收集整理的网格中的BFS，逆向(POJ2049)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。