DFS(迷宮最短路徑）

骨頭的誘惑者

時間限制：2000/1000 MS（Java / Others）記憶體限制：65536/32768 K（Java / Others）

總送出内容：166747接受的送出内容：44256

問題描述

小狗在一個古老的迷宮中發現了一塊骨頭，這讓他很着迷。然而，當他拿起它時，迷宮開始搖晃，小狗可以感覺到地面下沉。他意識到骨頭是一個陷阱，他拼命想要擺脫這個迷宮。

迷宮是一個大小為N×M的矩形。迷宮中有一扇門。在開始時，門被關閉，它将在第T秒開啟一小段時間（不到1秒）。是以，小狗必須在第T秒才到達門口。在每一秒中，他可以将一個塊移動到上，下，左和右相鄰塊之一。一旦他進入一個區塊，這個區塊的地面将開始下沉并在下一秒消失。他不能在一個街區停留一秒以上，也不能進入一個被通路的街區。這隻可憐的小狗能活下來嗎？請幫幫他。

輸入

輸入包含多個測試用例。每個測試用例的第一行包含三個整數N，M和T（1 <N，M <7; 0 <T <50），分别表示迷宮的大小和門打開的時間。 。接下來的N行給出迷宮布局，每行包含M個字元。角色是下列之一：

'X'：一塊牆，小狗不能進入; 

'S'：小狗的起點; 

'D'：門; 或

'。'：空塊。

輸入以三個0結束。不處理此測試用例。

産量

對于每個測試用例，如果小狗可以存活，則在一行中列印“是”，否則列印為“否”。

樣本輸入

4 4 5 SX ..X。 ..XD .... 3 4 5 SX ..X。 ...... D 0 0 0

樣本輸出

#include <iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int dr[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int f[10][10];
char mp[10][10];
int sx,sy,tx,ty,t,n,m,i,j;
int check(int x,int y)
{
    if (x>=0 && x<n && y>=0 && y<m && mp[x][y]!='X' && !f[x][y]) return 1;
      else return 0;
}
int  dfs(int x,int y,int time)
{
    if (time==0 && x==tx && y==ty)
           return 1;
    for(int i=0;i<4;i++)
    {
        int xx=x+dr[i][0];
        int yy=y+dr[i][1];
        if (check(xx,yy))
        {
            f[xx][yy]=1;
            if (dfs(xx,yy,time-1)) return 1;
            f[xx][yy]=0;
        }
    }
    return 0;
}

int main()
{
    while(scanf("%d%d%d",&n,&m,&t) && n!=0)
    {
        for(i=0;i<n;i++)
            {
                scanf("%s",&mp[i]);
                for(j=0;j<m;j++)
                    if (mp[i][j]=='S') sx=i,sy=j;
                       else if (mp[i][j]=='D') tx=i,ty=j;
            }
       if (t==0)
       {
            if (sx!=tx && sy!=ty) printf("NO\n");
              else if (sx==tx && sy==ty) printf("YES\n");
            continue;
       }
       if (abs(tx-sx)+abs(ty-sy)>t || (t-abs(tx-sx)-abs(ty-sy))%2!=0) {printf("NO\n");continue;}

       memset(f,0,sizeof(f));
       f[sx][sy]=1;
       if (dfs(sx,sy,t)) printf("YES\n");
                else printf("NO\n");
    }

    return 0;
}