DOJ 1010 Tempter of the Bone （DFS）

 1 //这个代码是没有考虑任何剪枝的
 2 //将所以情况都遍历了一遍，
 3 //提交的时候是会超时的  Time Limit Exceeded
 4 #include<iostream>
 5 #include<string.h>
 6 using namespace std;
 7 
 8 #define MAX 10
 9 char mapz[MAX][MAX];
10 int N,M,T;
11 int dx, dy;
12 bool escape;
13 
14 void dfs(int sx, int sy,int t)
15 {
16     if(sx <=0 || sx >N || sy <= 0 || sy > M)
17         return;
18     if(escape == true ||( sx == dx && sy ==dy && t == 0 ))
19     {
20         escape =true;
21         return;
22     }    
23     mapz[sx][sy] = 'X';
24     if(mapz[sx+1][sy] != 'X')
25     {
26         dfs(sx+1,sy,t-1);
27         if(escape) return;
28     }
29     if(mapz[sx][sy+1] != 'X')
30     {
31         dfs(sx,sy+1,t-1);
32         if(escape) return;
33     }
34     if(mapz[sx-1][sy] != 'X')
35     {
36         dfs(sx-1,sy,t-1);
37         if(escape) return;
38     }
39     if(mapz[sx][sy-1] != 'X')
40     {
41         dfs(sx,sy-1,t-1);
42         if(escape) return;
43     }
44     mapz[sx][sy] = '.';
45 }
46 
47 
48 int main()
49 {
50     int sx,sy,i,j;
51     while(scanf("%d%d%d",&N,&M,&T)!=EOF)
52     {
53         if(N == 0&& M == 0 &&T == 0)
54          continue;
55          getchar();
56         for(i=1;i<=N;i++)
57         {
58             for(j=1;j<=M;j++)
59             {
60                 scanf("%C", &mapz[i][j]);
61                 if(mapz[i][j] == 'S')
62                 {sx = i; sy = j;}
63                 else if(mapz[i][j] == 'D')
64                 {dx = i; dy = j;}
65             }
66             getchar();
67         }
68         escape =false;
69         dfs(sx,sy,T);
70         if(escape)
71         printf("YES\n");
72         else
73         printf("NO\n");
74     }
75 }

//接下来就要考虑剪枝了
//每个block只能走一次
//要求恰好某个给定的时间到达出口
//如果可走的block的总数小于时间，将会产生什么情况？

/*
可以把map看成这样： 
0 1 0 1 0 1 
1 0 1 0 1 0 
0 1 0 1 0 1 
1 0 1 0 1 0 
0 1 0 1 0 1 
从为 0 的格子走一步，必然走向为 1 的格子 
从为 1 的格子走一步，必然走向为 0 的格子 
即： 
 0 ->1或1->0 必然是奇数步 
 0->0 走1->1 必然是偶数步 
结论
所以当遇到从 0 走向 0 但是要求时间是奇数的，或者， 从 1 走向 0 但是要求时间是偶数的 都可以直接判断不可达！

*/
/*
那么设所在位置 (x,y) 与 目标位置 (dx,dy)
如果abs(dx-x)+abs(dy-y) 为偶数，则说明 abs(dx-x)+和 abs(dy-y)的奇偶性相同，需要走偶数步
如果abs(dx-x)+abs(dy-y)为奇数，那么说明 abs(dx-x)和 abs(dy-y)的奇偶性不同，需要走奇数步
解为 abs(dx-sx)+abs(dy-sy)的奇偶性就确定了所需要的步数的奇偶性！！
而 (ti-setp)表示剩下还需要走的步数，由于题目要求要在 ti时 恰好到达，那么  (ti-step) 
与 abs(x-y)+abs(dx-dy) 的奇偶性必须相同
因此 temp=ti-step-abs(dx-x)-abs(dy-y) 必然为偶数！

*/

#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;

#define MAX 10
char mapz[MAX][MAX];
int N,M,T;
int dx, dy;
bool escape;

void dfs(int sx, int sy,int t)
{
    if(sx <=0 || sx >N || sy <= 0 || sy > M)
        return;
    if(escape == true ||( sx == dx && sy ==dy && t == 0 ))
    {
        escape =true;
        return;
    }    
    //------------------------------------
    int tmp = t - abs(sx-dx) - abs(sy - dy);
    if (tmp < 0|| tmp&1)
    return;                                        //这里就是奇偶性剪枝 
    //------------------------------------
    mapz[sx][sy] = 'X';
    if(mapz[sx+1][sy] != 'X')
    {
        dfs(sx+1,sy,t-1);
        if(escape) return;
    }
    if(mapz[sx][sy+1] != 'X')
    {
        dfs(sx,sy+1,t-1);
        if(escape) return;
    }
    if(mapz[sx-1][sy] != 'X')
    {
        dfs(sx-1,sy,t-1);
        if(escape) return;
    }
    if(mapz[sx][sy-1] != 'X')
    {
        dfs(sx,sy-1,t-1);
        if(escape) return;
    }
    mapz[sx][sy] = '.';        //回溯 
}


int main()
{
    int sx,sy,i,j;
    while(scanf("%d%d%d",&N,&M,&T)!=EOF)
    {
        if(N == 0&& M == 0 &&T == 0)
         continue;
         getchar();
        //--------------
         int wall = 0;
        //-------------- 
        for(i=1;i<=N;i++)
        {
            for(j=1;j<=M;j++)
            {
                scanf("%C", &mapz[i][j]);
                if(mapz[i][j] == 'X')
                    wall++;
                if(mapz[i][j] == 'S')
                {sx = i; sy = j;}
                else if(mapz[i][j] == 'D')
                {dx = i; dy = j;}
            }
            getchar();
        }
        escape =false;
        //---------------------------------------- 这里是  可走的block的总数小于时间
        if(N*M-wall <= T)
        {
            printf("NO\n");
            continue;        
        }
        //---------------------------------------- 
        dfs(sx,sy,T);
        if(escape)
        printf("YES\n");
        else
        printf("NO\n");
    }
}

//
void DfsSerch(int x,int y,int step)
{
   int temp;
   temp=ti-step-abs(dx-x)-abs(dy-y);
   if (temp<0||temp%2==1) return;
   int tx,ty;
   for(int i=0;i<4;i++)  //四个方向探索 上下左右走 
  {
      tx=x+dir[i][0];   ty=y+dir[i][1];
      if (a[tx][ty]=='D'&&step==ti-1)
      { flag=1;   return ; }
      if(a[tx][ty]=='.'&&(tx>=0&&tx<n)&&(ty>=0&&ty<m))
      {
         a[tx][ty]='X';  //标记访问 
         DfsSerch(tx,ty,step+1);
         a[tx][ty]='.';  //回溯取消标记
         if(flag==1) return;//找到直接返回
      }
   }
}