hdu 1010 dfs+剪枝

剪枝还是挺多的，不过都比较容易想，主要是复习一下奇偶性剪枝。
 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <cmath>
 5 using namespace std;
 6 
 7 const int N = 7;
 8 char maze[N][N];
 9 int dx[] = { 0, 0, 1, -1 };
10 int dy[] = { 1, -1, 0, 0 };
11 int sx, sy, ex, ey;
12 int n, m, t, wall;
13 
14 bool ok( int x, int y )
15 {
16     return x >= 0 && x < n && y >= 0 && y < m && maze[x][y] == '.';
17 }
18 
19 bool dfs( int x, int y, int step )
20 {
21     if ( step == t )
22     {
23         if ( x == ex && y == ey ) return true;
24         return false;
25     }
26     int d1 = abs( ex - x ) + abs( ey - y );
27     int d2 = abs( t - step );
28     if ( d2 < d1 ) return false;
29     for ( int i = 0; i < 4; i++ )
30     {
31         int xx = x + dx[i];
32         int yy = y + dy[i];
33         if ( ok( xx, yy ) )
34         {
35             maze[xx][yy] = 'X';
36             if ( dfs( xx, yy, step + 1 ) ) return true;
37             maze[xx][yy] = '.';
38         }
39     }
40     return false;
41 }
42 
43 int main ()
44 {
45     while ( scanf("%d%d%d", &n, &m, &t) != EOF )
46     {
47         if ( !n && !m && !t ) break;
48         wall = 0;
49         for ( int i = 0; i < n; i++ )
50         {
51             scanf("%s", maze[i]);
52             for ( int j = 0; j < m; j++ )
53             {
54                 if ( maze[i][j] == 'S' )
55                 {
56                     sx = i;
57                     sy = j;
58                     maze[i][j] = 'X';
59                     wall++;
60                 }
61                 else if ( maze[i][j] == 'D' )
62                 {
63                     ex = i;
64                     ey = j;
65                     maze[i][j] = '.';
66                 }
67                 else if ( maze[i][j] == 'X' )
68                 {
69                     wall++;
70                 }
71             }
72         }
73         int d = abs( ex - sx ) + abs( ey - sy );
74         if ( ( d & 1 ) == ( t & 1 ) && n * m - wall >= t )
75         {
76             if ( dfs( sx, sy, 0 ) )
77             {
78                 puts("YES");
79             }
80             else
81             {
82                 puts("NO");
83             }
84         }
85         else
86         {
87             puts("NO");
88         }
89     }
90     return 0;    
91 }