HDOJ-1010 Tempter of the Bone（dfs）

 Description：

探险者在一个古老的迷宫中发现了一个珠宝，，当他捡起它时，迷宫开始摇晃，探险者可以感觉到地面下沉。他意识到珠宝是一个陷阱，他拼命试图摆脱这个迷宫。

迷宫是一个矩形，大小为N×M。迷宫中有一扇门。刚开始时，门是关闭的，他将在第T秒打开一小段时间（少于1秒）。因此，他必须在第T秒精确到达门。每秒钟，他可以将一个块移动到上，下，左和右相邻的块之一。一旦他进入一个砖块，该砖块的地面将开始下沉并在下一秒消失。他不能在一个砖块停留超过一秒钟，也不能搬到一个拜访的砖块。

输入：
4 4 5
S.X.
..X.
..XD
....
3 4 5
S.X.
..X.
...D
0 0 0
输出：
NO
YES

 简单DFS模板题，个人建议用cin输入，代码如下：

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<conio.h>
using namespace std;

char map[20][20];
int data[20][20]= {99999};
int t;
bool num;
void visit(int n,int m,int cot,int x,int y,int t)
{
  if(cot > t)
    return ;
  else if(cot == t && data[n][m] == 4)
   {
    num = true;
    return;
   }
  else if(data[n][m]==1||data[n][m]==2)
  {
          data[n][m] = 3;
          if(m+1<y&&(data[n][m+1]==2||data[n][m+1]==4)) visit(n,m+1,cot+1,x,y,t);
          if(m-1>=0&&(data[n][m-1]==2||data[n][m-1]==4)) visit(n,m-1,cot+1,x,y,t);
          if(n+1<x&&(data[n+1][m]==2||data[n+1][m]==4)) visit(n+1,m,cot+1,x,y,t);
          if(n-1>=0&&(data[n-1][m]==2||data[n-1][m]==4)) visit(n-1,m,cot+1,x,y,t);
          data[n][m] = 2;
  }
}

int main()
{
    int n,m,t;
    while((cin>>n>>m>>t)&&(n!=0&&m!=0&&t!=0))
    {
        int x1;
        int y1;
        num = false;
        memset(data,99999,sizeof(data));
        memset(map,'0',sizeof(map));
        for(int i=0 ;i<n; i++)
        {

            for(int j=0 ;j< m; j++)
            {
             cin>>map[i][j];
            // printf("%d %d
",i,j);
             if(map[i][j] == 'S')
            {
                x1 = i;
                y1 =j;
                data[i][j] = 1;
            }
              else if(map[i][j]=='.')
              {
                  data[i][j]=2;
              }
              else if(map[i][j]=='X')
              {
                  data[i][j] = 3;
              }
              else if(map[i][j] =='D')
                data[i][j] = 4;
            }
        }
        visit(x1,y1,0,n,m,t);
        if(num)
            printf("YES
");
        else printf("NO
");
    }
}