超级无语，这样的题居然花了我这么久时间。头脑不清醒～～～ 本来一拿到题目是要用广搜的。头脑不知道一下子怎么短路了，明知道深搜会超时还是用了深搜！ 后来想想还是广搜。#include<stdio.h> #include<limits.h> #define MAX 205 int a[MAX][MAX];//路形 int mark[MAX][MAX];//是否已搜标志 int f[1011][2];//搜索队列 int MIN[MAX][MAX]; int d[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//4个方向 int main() {     char c;     int M,N,i,j;     int p,rear,dd;     int si,sj,di,dj;      while(scanf("%d%d",&M,&N)!=EOF)     {         for(i=0;i<M;i++)         {            scanf("%c",&c);            for(j=0;j<N;j++)            {                mark[i][j]=0;                MIN[i][j]=INT_MAX;                scanf("%c",&c);                if(c=='#')                    a[i][j]=-1;                else if(c=='.') a[i][j]=0;                else if(c=='x') a[i][j]=1;//警                else if(c=='a')                {                    di=i;                    dj=j;                }                else if(c=='r')                {                    si=i;                    sj=j;                }             }         }//for i         f[0][0]=si;         f[0][1]=sj;   MIN[si][sj]=0;         p=0;         rear=0;         while(p<=rear)         {             for(dd=0;dd<4;dd++)             {                 si=f[p][0]+d[dd][0];                 sj=f[p][1]+d[dd][1];                 if(si==di&&sj==dj)                 {      if(MIN[f[p][0]][f[p][1]]+1<MIN[di][dj])       MIN[di][dj]=MIN[f[p][0]][f[p][1]]+1;                 }                 if(si>=0&&si<M&&sj>=0&&sj<N&&a[si][sj]==1&&mark[si][sj]==0)                 {                     mark[si][sj]=1;                     rear++;                                f[rear][0]=si;                     f[rear][1]=sj;               MIN[f[rear][0]][f[rear][1]]=MIN[f[p][0]][f[p][1]]+2;                 }     else if(si>=0&&si<M&&sj>=0&&sj<N&&a[si][sj]==1&&MIN[f[p][0]][f[p][1]]+2<MIN[si][sj])//&&MIN[f[p][0]][f[p][1]]<INT_MIN-1)     {      MIN[si][sj]=MIN[f[p][0]][f[p][1]]+2;     }     if(si>=0&&si<M&&sj>=0&&sj<N&&a[si][sj]==0&&mark[si][sj]==0)                 {                     mark[si][sj]=1;                     rear++;                                f[rear][0]=si;                     f[rear][1]=sj;      MIN[f[rear][0]][f[rear][1]]=MIN[f[p][0]][f[p][1]]+1;                 }     else if(si>=0&&si<M&&sj>=0&&sj<N&&a[si][sj]==0&&MIN[f[p][0]][f[p][1]]+1<MIN[si][sj])//&&MIN[f[p][0]][f[p][1]]<INT_MIN-1)     {      MIN[si][sj]=MIN[f[p][0]][f[p][1]]+1;     }    }             p++;         }         if(MIN[di][dj]==INT_MAX)         {             printf("Poor ANGEL has to stay in the prison all his life.\n");         }   else printf("%d\n",MIN[di][dj]);     }     return 0; }

评论