学步园

//多个起点，要最短得目标，不妨倒过来从目标出发，去找最近的点更新！！！！！！递归时思路要清楚

#include<iostream>
#include<cstring>
using namespace std;
int a[202][202]; int ax,ay;int f[4][2]={0,1,1,0,-1,0,0,-1};int mmin=50000;int visit[202][202];
 void dfs(int x,int y,int count)     
 {
     if(a[x][y]==0)return;
     else if(a[x][y]==2)count=count+2;         //步数计数！不同情况。每次走一步深一层时计数
     else count++;
     if(a[x][y]==4)                            //出口！
     {
         if(count<mmin)mmin=count;
     }
     else
     {
         for(int i=0;i<4;i++)                   //走
         {
             if(visit[x][y]==0&&a[x][y]!=0)      //没访问或者不被限制的
            {
             visit[x][y]=1;
             dfs(x+f[i][0],y+f[i][1],count);      //如此深入
             visit[x][y]=0;
            }
         }
     }
 }
int main()
{
   int n,m;
   while(cin>>n>>m)
   {
       memset(a,0,sizeof(a));
       memset(visit,0,sizeof(0));
       int i,j;
       mmin=50000;
       char s;
       for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
          {
              cin>>s;
              if(s=='a')
              {
                  ax=i;ay=j;a[i][j]=3;
              }
              else if(s=='r') a[i][j]=4;
              else if(s=='.')  a[i][j]=1;
              else if(s=='x') a[i][j]=2;
          }
       dfs(ax,ay,0);
       if(mmin==50000)cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;
       else  cout<<mmin-1<<endl;
   }
}
//下面是BFS：
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int a[202][202]; int ax,ay;int f[4][2]={0,1,1,0,-1,0,0,-1};int mmin=50000;int visit[202][202];
struct state
{
    int x,y;
    int count;
   state(){count=0;}
};
 void bfs(state aa)
 {
     queue<state>q;       
     q.push(aa);
     while(!q.empty())      
     {
         state now=q.front();      //对队头元素分析
         visit[now.x][now.y]=1;     //标记访问
         q.pop();
         if(a[now.x][now.y]==4)    //更新
         {
             if(now.count<mmin)mmin=now.count;
         }
        else
        {
          for(int i=0;i<4;i++)       //队头拉出其他元素
          {
            state next;
            next.x=now.x+f[i][0],next.y=now.y+f[i][1] ;     //没访问或者不被限制的
            if(a[next.x][next.y]==1||a[next.x][next.y]==4)next.count=now.count+1;
            else if(a[next.x][next.y]==2)next.count=now.count+2;
            if(visit[next.x][next.y]==0&&a[next.x][next.y]!=0)
            {
               q.push(next);
            }
           }
        }
     }
 }
int main()
{
   int n,m;
   while(cin>>n>>m)
   {
       memset(a,0,sizeof(a));
       memset(visit,0,sizeof(visit));
       int i,j;
       mmin=50000;
       char s;
       for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
          {
              cin>>s;
              if(s=='a')
              {
                  ax=i;ay=j;a[i][j]=3;
              }
              else if(s=='r') a[i][j]=4;
              else if(s=='.')  a[i][j]=1;
              else if(s=='x') a[i][j]=2;
          }
        state aa;
        aa.x=ax;aa.y=ay;aa.count=0;
       bfs(aa);
       if(mmin==50000)cout<<"Poor ANGEL has to stay in the prison all his life."<<endl;
       else  cout<<mmin<<endl;
   }
}