题目链接：

第二次做这个题目了，结果没仔细读题，直接就BFS了， 原来是求是否恰好在T 秒逃出迷宫， 而不是T秒内；

上次做是在刚学习搜索的时候，看样子印象还是不够深刻，奇偶剪枝也忘得差不多了，故在写一篇博客；

先介绍一下奇偶剪枝， 

首先举个例子，有如下4*4的迷宫，'.'为可走路段，'X'为障碍不可通过

S...

....

....

...D

从S到D的最短距离为两点横坐标差的绝对值+两点纵坐标差的绝对值 = abs(Sx - Dx) + abs(Sy - Dy) = 6，这个应该是显而易见的。

遇到有障碍的时候呢

S.XX

X.XX

...X

...D

你会发现不管你怎么绕路，最后从S到达D的距离都是最短距离+一个偶数，这个是可以证明的

而我们知道：

奇数 + 偶数 = 奇数

偶数 + 偶数 = 偶数

因此不管有多少障碍，不管绕多少路，只要能到达目的地，走过的距离必然是跟最短距离的奇偶性是一致的。

                                                                                                                                                                                  以上转自博主： 

所以对于本题而言，设MinDistance =abs(Sx - Dx) + abs(Sy - Dy)；  本题给的时间T ;

只要        MinDistance-T     是偶数则能够到达，是奇数就直接舍弃了   ;

【AC代码】

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;int n,m,t;char map[10][10];int dx[4]={0,0,1,-1};int dy[4]={1,-1,0,0};int stx,sty,endx,endy;struct co{ int x,y; int step;};bool dfs(co a){ co b; if(a.x==endx&&a.y==endy&&a.step==t) return true; for(int i=0;i<4;i++) { b.x=a.x+dx[i]; b.y=a.y+dy[i]; b.step=a.step+1; if(b.x<0||b.y<0||b.x>n-1||b.y>m-1||map[b.x][b.y]=='X'||b.step>t) continue; else { map[b.x][b.y]='X'; if(dfs(b)) return true; else { map[b.x][b.y]='.'; continue; } } } return false;}int main(){ while(cin>>n) { cin>>m>>t; if(n==0) break; for(int i=0;i
          
           >map[i][j]; if(map[i][j]=='S') { stx=i;sty=j; } if(map[i][j]=='D') { endx=i;endy=j; } } } int ans=(abs(stx-endx)+abs(sty-endy)-t) ;//奇偶剪枝 if( ans%2) cout<<"NO"<
          
         
        
       
      
     
    

                                                                                               

后来参照了大神的代码，发现他们能不用剪枝，就能将时间优化到500ms；

【大神代码】

#include 
    
     #include 
     
      #include 
      
       using namespace std;char maze[10][10];bool dfs(int x, int y, int T){    // 剩一步时即可判断是否为出口，找到返回true    if (T == 1){        if (maze[x-1][y] == 'D') return true;        if (maze[x+1][y] == 'D') return true;        if (maze[x][y-1] == 'D') return true;        if (maze[x][y+1] == 'D') return true;        return false;    }    else{        // 标记走过        maze[x][y] = 'X';        // 深度优先搜索        if (maze[x-1][y] == '.' && dfs(x-1, y, T-1)) return true;         if (maze[x+1][y] == '.' && dfs(x+1, y, T-1)) return true;        if (maze[x][y-1] == '.' && dfs(x, y-1, T-1)) return true;        if (maze[x][y+1] == '.' && dfs(x, y+1, T-1)) return true;        // 还原走过        maze[x][y] = '.';        return false;    }}int main(){    int sx,sy,gx,gy;    int N,M,T;    while(cin>>N>>M>>T,T){        memset(maze,'X',sizeof(maze));        for(int i=0;i
       
        >maze[i][j];                if(maze[i][j]=='S')                    sx=i,sy=j;                else if(maze[i][j]=='D')                    gx=i,gy=j;            }        }       // if( ( abs(sx-gx)+abs(sy-gy) - T ) & 1 )        //奇偶剪枝         //   cout<<"NO"<