ZOJ 1002 Fire Net

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1002

分析：类八皇后问题，简单DFS。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 
 5 char map[8][8];
 6 int n;
 7 int max;
 8 
 9 bool check( int x, int y )
10 {
11     for ( int i = x - 1; i > 0; i-- ) if ( map[i][y] == '*' ) return false;
12         else if ( map[i][y] == 'X' ) break;
13 
14     for ( int i = x + 1; i <= n; i++ ) if ( map[i][y] == '*' ) return false;
15         else if ( map[i][y] == 'X' ) break;
16 
17     for ( int j = y - 1; j >= 0; j-- ) if ( map[x][j] == '*' ) return false;
18         else if ( map[x][j] == 'X' ) break;
19 
20     for ( int j = y + 1; j <= n; j++ ) if ( map[x][j] == '*' ) return false;
21         else if ( map[x][j] == 'X' ) break;
22 
23     return true;
24 }
25 
26 void DFS( int x, int y, int sum )
27 {
28  //   printf( "x = %d, y = %d, sum = %d\n", x, y, sum );
29     if ( x == n && y == n )
30     {
31         if ( map[x][y] != 'X' && check( x, y ) ) ++sum;
32         if ( sum > max ) max = sum;
33         return;
34     }
35 
36     if ( map[x][y] == '.' && check( x, y ) )
37     {
38         for ( int i = x; i <= n; i++ )
39             for ( int j = 1; j <= n; j++ )
40             {
41                 if ( i == x && j == y ) continue;
42                 map[x][y] = '*';
43                 DFS( i, j, sum + 1 );
44                 map[x][y] = '.';
45             }
46     }
47     return;
48 }
49 
50 int main()
51 {
52   //  freopen( "s.out", "w", stdout );
53     while ( scanf( "%d", &n ), n )
54     {
55         memset( map, 'X', sizeof(map) );
56         for ( int i = 0; i < 8; i++ )
57             map[i][7] = '\0';
58 
59         for ( int i = 1; i <= n; i++ )
60         {
61             getchar();
62             for ( int j = 1; j <= n; j++ )
63                 map[i][j] = getchar();
64         }
65 
66         max = 0;
67         for ( int i = 1; i <= n; i++ )
68             for ( int j = 1; j <= n; j++ )
69                 if ( map[i][j] == '.' )  DFS( i, j, 0 );
70         printf( "%d\n", max );
71     }
72     return 0;
73 }

=======

最近想好好练练搜索……之前练的完全忘光光了，就从最简单的开始吧……