hdu1242 Rescue

#include<stdio.h>
#include<string.h>
#include<limits.h>
#include<queue>
using namespace std;

const int maxn=205;

char g[maxn][maxn];
unsigned int num[maxn][maxn];
int move[][2]={{-1,0},{0,-1},{1,0},{0,1}};
struct point
{
    int x,y;
    point(){}
    point(int a,int b):x(a),y(b){}
};

int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        int i,j;
        point temp;
        memset(num,-1,sizeof(num));     
        
        for(i=0;i<n;i++)
        {
            scanf("%s",g[i]);
            for(j=0;j<m;j++)
            {
                if(g[i][j]=='a')   

                {
                    temp.x=i;
                    temp.y=j;
                }
            }
        }
        
        queue<point> que;
        que.push(temp);
        num[temp.x][temp.y]=0;

        while(!que.empty())
        {
            temp=que.front();
            que.pop();

            for(i=0;i<4;i++)
            {
                int newx=temp.x+move[i][0];
                int newy=temp.y+move[i][1];
                if(newx<0||newx>=n||newy<0||newy>=m)            
                    continue;
                if(g[newx][newy]=='#')
                    continue;
                int count=1;
                if(g[newx][newy]=='x')
                    count++;
                if(num[temp.x][temp.y]+count<num[newx][newy])
                {
                    num[newx][newy]=num[temp.x][temp.y]+count;
                    que.push(point(newx,newy));
                }
            }
        }
        
        unsigned int opt=UINT_MAX;
        for(i=0;i<n;i++)
            for(j=0;j<m;j++)
            {
                if(g[i][j]=='r'&&num[i][j]<opt)
                {
                    opt=num[i][j];
                }
            }

        if(opt==UINT_MAX)
        {
            printf("Poor ANGEL has to stay in the prison all his life.\n");
        }
        else
        {
            printf("%u\n",opt);
        }
    }
    return 0;
}


程序说明：

1,必须从'a'开始bfs，因为可能存在多个'r'，若从'r'开始搜索则变复杂了。

2,必须初始每个位置的深度为最大，因为在bfs时存在比较和广搜的顺序问题，这样可以在搜索时逐渐将每个位置更新为最小值。

3,不能在广搜一搜到'r'就break，因为在搜索时存在搜索方向的先后问题，即dir数组的值的顺序，这样就可能存在后搜到的值可能比先搜到的值更小