ACM___________________________

所謂路徑剪枝:  

    矩陣的大小是N*M 墻的數(shù)量記為wall 如果能走的路的數(shù)量 N*M - wall 小于時(shí)間T,就是說走完也不能到總的時(shí)間的,這顯然是錯(cuò)誤的,可以直接跳出了.

   另外還有就是, 當(dāng)DFS深度 > T 時(shí),顯然也不用繼續(xù)找下去了. 那狗已經(jīng)掛了. 

所以在經(jīng)過這3次剪枝后, 時(shí)間就大大縮短了. 

值得一提的是!!! 這題我WA了很久, 一直找不原因,  因?yàn)閿?shù)據(jù)不一定是按嚴(yán)格矩陣排列的!! 也可能都在一行!!!! 所以 無論是 gets 還是 getchar 都錯(cuò)的很冤枉.

使用 cin  和 scanf ("%s") 后 AC 了, 在此感謝 AMB神牛的幫忙....... 

代碼如下:

 /*

MiYu原創(chuàng), 轉(zhuǎn)帖請(qǐng)注明 : 轉(zhuǎn)載自 ______________白白の屋

Author By : MiYu

Test      : 1

Program   : HDU1010

*/

#include <iostream>

#include <ctime>

using namespace std;

typedef struct pos{

       int x,y;

       void setPos( int a = 0,int b = 0 ){ x = a; y = b; }

}POS; 

POS start,end;

const int START = 10;  //看了就知道啥意思 

const int DOOR = 20;

const int WALL = 0;

const int ROAR = 1;

int N = 0,M = 0,T = 0; //輸入的 

int maze[11][11];      //很明顯是迷宮地圖 

int d[4][2] = { { 0,1 },{ 1,0 },{ 0,-1 },{ -1,0 } };

int f = 1,roarCount = 0;  //標(biāo)記是否找到路 , 記錄可以走的路的個(gè)數(shù) 

int DFS ( int x,int y,int n )

{

    if ( n == T )     //時(shí)間用完了, 走到出口沒 ? 

    {

         if ( x == end.x && y == end.y )

              f = 0;

         return 0;  

    }

    if ( f == 0 )     //已經(jīng)找到路了, 不用找了  

         return 0;

    int t = T - n - abs( x-end.x ) - abs( y-end.y );   

    if ( t < 0 || t % 2 == 1 )     //不夠時(shí)間了 或 不可能走到(奇偶剪枝)

         return 0;  

    for ( int i = 0; i != 4; ++ i )

    {

          if ( maze[ x+d[i][0] ][ y+d[i][1] ] != WALL )    //先看看下一步能不能走 

          {

                     maze[x+d[i][0]][y+d[i][1]] = WALL;    //走過后就不能走了 

                     DFS ( x+d[i][0], y+d[i][1], n + 1 );  //走到下一個(gè)位置 

                     if ( f == 0 )     //已經(jīng)找到路了, 不用找了  

                          return 0; 

                     maze[x+d[i][0]][y+d[i][1]] = ROAR;    //沒找到路,回溯下 

          }

    } 

    return 0;

}

void init()  //在主函數(shù)一堆, 難看, 放外面了, 不解釋 

{

     memset ( maze, 0, sizeof ( maze ) );

     f = 1, roarCount = 0;

     for ( int i = 1; i <= N; ++ i )

     {

           char ch;

           for ( int j = 1; j <= M ; ++ j )

           {           

                 cin >> ch;

                 switch ( ch )

                 {

                         case 'S':  maze[i][j] = START; start.setPos ( i,j ); break;

                         case '.':  maze[i][j] = ROAR;  roarCount ++; break;

                         case 'X':  maze[i][j] = WALL;  break;              

                         case 'D':  maze[i][j] = DOOR;  end.setPos ( i,j ); roarCount ++; break;

                 }

           } 

     }      

}

int main ()

{

    while ( cin >> N >> M >> T, N + M + T )

    {

           init ();

           if ( roarCount >= T )      //當(dāng)然要保證能走的路比開門的時(shí)間要多 

           {

                maze[start.x][start.y] = WALL;

                DFS( start.x, start.y, 0 );

           }  

           puts ( f == 1 ? "NO" : "YES" );

    }

    return 0;

}

另外附上一網(wǎng)友詳細(xì)解釋: