题意：一只小狗要刚好在t时刻从起点都到终点，问可不可以。

注意剪枝。

 

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 int maze[9][9]; 6 bool vis[9][9]; 7 int n,m,t; 8 bool ans; 9 struct Point10 {11     int x,y;12 };13 int dx[4]={
    0,0,-1,1};14 int dy[4]={
    1,-1,0,0};15 Point p,e;16 void dfs(Point cur,int dep)17 {18     vis[cur.x][cur.y]=true;19     if(!ans&&cur.x==e.x&&cur.y==e.y&&dep==t)20     {21         ans=true;22         return ;23     }24     if(!ans&&dep>t)25         return ;26     for(int i=0;i<4;i++)27     {28         Point dcur;29         dcur.x=cur.x+dx[i];30         dcur.y=cur.y+dy[i];31         if(dcur.x<1||dcur.x>n||dcur.y<1||dcur.y>m)32             continue;33         if(vis[dcur.x][dcur.y])34             continue;35         if(!maze[dcur.x][dcur.y])36             continue;37         if(!ans)38         {39             dfs(dcur,dep+1);40             vis[dcur.x][dcur.y]=false;//注意回溯41         }42     }43 }44 int main()45 {46     while(scanf("%d%d%d",&n,&m,&t))47     {48         if(n==0&&m==0&&t==0)49             break;50         char s[15];51         for(int i=1;i<=n;i++)52         {53             scanf("%s",s+1);54             for(int j=1;j<=m;j++)55             {56                 if(s[j]=='X')57                     maze[i][j]=0;58                 else if(s[j]=='.')59                     maze[i][j]=1;60                 else if(s[j]=='S')61                 {62                     p.x=i;63                     p.y=j;64                     maze[i][j]=1;65                 }66                 else67                 {68                     e.x=i;69                     e.y=j;70                     maze[i][j]=1;71                 }72             }73         }74         ans=false;75         memset(vis,false,sizeof(vis));76         int a=abs(e.x+e.y-p.x-p.y);77         if(a>t)    //剪枝78             ans=false;79         else if(a%2!=t%2)   //剪枝80             ans=false;81         else82             dfs(p,0);83         if(ans)84             printf("YES\n");85         else86             printf("NO\n");87     }88     return 0;89 }