hdu--1010--dfs

话说这题是所谓的最最经典的dfs...

反正它让我学会了奇偶剪枝传送

感觉这边会让你看懂奇偶剪枝它很详细的解释了为什么是偶数的由来

其他关于这题就没什么好讲的了就注意下是恰好t秒

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 
 5 int n , m , t;
 6 int endx , endy;
 7 bool flag;
 8 char maze[10][10];
 9 bool vis[10][10];
10 int dir[4][2]={1,0,-1,0,0,1,0,-1};
11 int abs( int x )
12 {
13     return x>0?x:-x;
14 }
15 
16 void dfs( int x , int y , int cnt )
17 {
18     if( cnt>t || x<0 || x>=n || y<0 || y>=m || flag )
19         return;
20      int temp = t - cnt - abs(x - endx) - abs(y - endy);
21     if( temp < 0 || temp & 1)
22         return;
23     if( maze[x][y] == 'D' && t == cnt )
24     {
25         flag = true;
26         return;
27     }
28     for( int i = 0 ; i<4 ; i++ )
29     {
30         int xx = x + dir[i][0];
31         int yy = y + dir[i][1];
32         if( maze[xx][yy]!='X' && !vis[xx][yy] )
33         {
34             vis[xx][yy] = true;
35             dfs( xx , yy , cnt+1 );
36             if( flag )
37                 return;
38             vis[xx][yy] = false;
39         }
40     }
41     return;
42 }
43 
44 int main()
45 {
46     int block , stx , sty;
47     while( cin >> n >> m >> t )
48     {
49         flag = false;
50         block = 0;
51         if( !n && !m && !t )
52             break;
53         memset( vis , false , sizeof(vis) );
54         for( int i = 0 ; i<n ; i++ )
55         {
56             for( int j = 0 ; j<m ; j++ )
57             {
58                 cin >> maze[i][j];
59                 if( maze[i][j] == 'S' )
60                 {
61                     stx = i;
62                     sty = j;
63                     vis[stx][sty] = true;
64                 }
65                 else if( maze[i][j] == 'D' )
66                 {
67                     endx = i;
68                     endy = j;
69                 }
70                 else if( maze[i][j] == '.' )
71                 {
72                     block++;
73                 }
74             }
75         }
76         if( block+1<t )
77         {
78             cout << "NO" << endl;
79             continue;
80         }
81         dfs( stx , sty , 0 );
82         if( flag )
83             cout << "YES" << endl;
84         else
85             cout << "NO" << endl;
86     }
87     return 0;
88 }

View Code

today:

　　我的床边放着的都是你送我的回忆

just follow your heart