題目傳送門：http://acm.hdu.edu.cn/showproblem.php?pid=1045

?

程序分析：

　　題目是說在一個特殊的地圖里擺設碉堡，限制條件可能跟N皇后又點相似，但是這里有墻，中間隔有墻的話還是不會互相干擾的。只是行列方向會沖突，斜角線不會沖突，。所以我們只有判斷所在的行列不會存在沖突的碉堡就行。注意中間可以隔有墻。記住每一次到達最后一個點時的可放碉堡數，比現在保存最大的就替換為最大值。

解決方法：

　　深搜回溯，找出每一種方法的最大放置碉堡數，編寫一個判斷能否放置碉堡的函數，細節看代碼。　　

?

?

View Code 1 #include<iostream> 2 #include<string> 3 using namespace std; 4 5 int n, m; 6 char map[5][5]; 7 int Max; 8 9 int pd(int x, int y) 10 { 11 for(int i=x-1; i>=0; i--) //判斷此行能否放置碉堡 12 { 13 if(map[i][y] == '0') 14 return 0; 15 if(map[i][y] == 'X') 16 break; 17 } 18 for(int j=y-1; j>=0; j--) //判斷此行能否放置碉堡 19 { 20 if(map[x][j] == '0') 21 return 0; 22 if(map[x][j] == 'X') 23 break; 24 } 25 return 1; 26 } 27 28 void DFS(int k, int curmax) 29 { 30 int x, y; 31 if(k == n*n) //到達最后一個點 32 { 33 if(Max < curmax) //保存這一種方法最多能擺的碉堡數 34 { 35 Max = curmax; 36 return ; 37 } 38 } 39 else 40 { 41 x = k/n; 42 y = k%n; 43 if(map[x][y]=='.' && pd(x, y)==1) //可以擺放就把個數加一繼續找下一個可以擺的地方 44 { 45 map[x][y] = '0'; 46 DFS(k+1, curmax+1); 47 map[x][y] = '.'; 48 } 49 DFS(k+1, curmax); //不能擺或者回溯回來進行下一個地方的查找 50 } 51 } 52 int main() 53 { 54 while(cin>>n && n) 55 { 56 for(int i=0; i<n; i++) 57 { 58 scanf("%s", map[i]); 59 } 60 Max = 0; 61 DFS(0, 0); 62 cout<<Max<<endl; 63 } 64 return 0; 65 }

?

轉載于:https://www.cnblogs.com/ruihua852/archive/2012/08/31/2664885.html

總結

以上是生活随笔為你收集整理的HDU-1045-fire net的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。