HDU1242 BFS

题意

给一个二维坐标的图，给出起点a和多个终点r，还给出一些特殊的块，经过这些块需要花费两步。求最短距离。

解法

广搜。有两种解法，一是遍历完整个图，记录最短的距离。二是用优先队列。遇到终点直接返回。这里我用前一种。这里用dx，dy两个数组表示行进的四个方向。易于阅读。 #include<cstdio> #include<queue> #include<cstring> using namespace std; int n,m,cnt; char g[205][205]; bool vis[205][205]; int dx[] = {0,0,-1,1}; int dy[] = {1,-1,0,0}; struct node{ int x,y,step; node(int a,int b,int c){x=a,y=b,step=c;} }; queue<node> q; void init() { cnt = 0; memset(vis,false,sizeof(vis)); while(!q.empty()) q.pop(); } void input() { for(int i=0;i<n;i++) scanf("%s",g[i]); } bool ok(node N) { int x = N.x; int y = N.y; if(x<m && x>=0 && y<n && y>=0) if(!vis[y][x]) if(g[y][x] != '#') return true; return false; } node getAngel() { for(int i=0;i<n;i++) for(int j=0;j<m;j++) if(g[i][j] == 'a') return node(j,i,0); } void bfs() { node Angel = getAngel(); vis[Angel.y][Angel.x] = true; q.push(Angel); while(!q.empty()) { node now = q.front();q.pop(); if(g[now.y][now.x] == 'r') cnt = max(cnt,now.step); for(int i=0;i<4;i++) { node next = node(now.x+dx[i], now.y+dy[i], now.step+1); if(g[next.y][next.x] == 'x') next.step++; if(ok(next)) { vis[next.y][next.x] = true; q.push(next); } } } } int main() { while(~scanf("%d%d",&n,&m)) { init(); input(); bfs(); if(cnt) printf("%d\n",cnt); else printf("Poor ANGEL has to stay in the prison all his life.\n"); } }