8皇后加墙版 ZOJ 1002 Fire Net

时间：2010-09-18 来源：sysuwhj

这题是 8皇后加墙版~ 现在我貌似回溯算法，都认为是dfs了~因为他们写起来框架都基本一样

这题卡了很久，尽管参照了8皇后解法，写的极其繁琐

主要是，分类讨论，当一个blockhouse放到矩阵里，它所在的行列都标记，然后再讨论，下一个要放的点，有4种情况（1行标记，列没标记 2 列标记，行没标记， 3 行列都标记了 4 行列都没标记）对这4种情况分别处理

后来，在网上看了别人的解题报告后，发现可以很简单就出来，参照其思路再写了一个，个人推荐这个，远比我自己想的简单~

Fire Net 简单版

 1 #include<iostream>
 2  using namespace std;
 3 
 4 
 5  char a[5][5];
 6  int n;
 7 int maxnum = 0;
 8 
 9 
10 void backtrack(int, int, int);
11 bool canbePlaced(int, int);
12 
13 int main()
14 {
15     
16     //freopen("test.txt", "r", stdin);
17     while(cin >> n && n)
18     {
19         for (int i = 0; i < n; i++)
20         {
21             for (int j = 0; j < n;j++)    
22                 cin >> a[i][j];            
23         }
24         maxnum = 0;
25         backtrack(0,0,0);
26         cout << maxnum << endl;
27     }
28     return 0;
29 }
30 
31 void backtrack(int x, int y, int count)
32 {
33     if (x == n)
34     {
35         if (count > maxnum)
36             maxnum = count;
37     }
38     else
39     {
40         if (y == n)
41             backtrack(x+1, 0, count);
42         else
43         {
44             if (a[x][y] == '.' && canbePlaced(x,y))
45             {
46                 a[x][y] = 'Y';
47                 backtrack(x, y+1,count+1);
48                 a[x][y] = '.';
49             }
50             backtrack(x,y+1,count);
51         }
52     }
53 }
54 
55 bool canbePlaced(int x, int y)
56 {
57     
58 
59     for (int i = x - 1; i >= 0; i--)
60     {
61         if (a[i][y] == 'Y')
62             return false;
63         if (a[i][y] == 'X')
64             break;
65     }
66 
67     for (int i = y - 1; i >= 0; i--)
68     {
69         if (a[x][i] == 'Y')
70             return false;
71         if (a[x][i] == 'X')
72             break;
73     }
74     return true;
75 }
76

Fire Net