題意：輸入一個n*m棋盤（0<n,m<10），某些格子有標記。用最少的皇后守衛所有帶標記的格子?；屎笠巹t是所在坐標的直線和斜線都可以被守衛，長度不限。

分析：因為不知道深度，所以用迭代加深搜索，判斷條件可以參照之前寫的八皇后問題。

具體就是回溯二分。

# include<iostream> # include<cstdio> # include<cmath> # include<map> # include<queue> # include<string> # include<string.h> #include<set> #include<list> # include<algorithm> using namespace std; int row, col; int maxd; char mp[10][10]; int vis[4][30]; bool judge() {for (int i = 0; i < row; i++)for (int j = 0; j < col; j++)if (mp[i][j]=='X' && !vis[0][j] && !vis[1][i] && !vis[2][i + j] && !vis[3][j - i + 10])return false;return true; } bool dfs(int cur,int count0) {if (count0 == maxd) {if (judge()) {return true;}else return false;}else {for (int k = cur; k < row*col; k++) {int i = k / col;int j = k % col;int n1 = vis[0][j]; int n2 = vis[1][i]; int n3 = vis[2][i + j]; int n4 = vis[3][j - i + 10];vis[0][j] = vis[1][i] = vis[2][i + j] = vis[3][j - i + 10] = 1;if (dfs(k, count0 + 1))return true;vis[0][j] = n1; vis[1][i] = n2; vis[2][i + j] = n3; vis[3][j - i + 10] = n4;}}return false;}int main() {string x; int kase = 0;while (scanf("%d", &row)&&row) {scanf("%d", &col);memset(mp, 0, sizeof(mp));memset(vis, 0, sizeof(vis));for (int i = 0; i < row; i++) {cin >> mp[i];}for (maxd = 0;; maxd++) {memset(vis, 0, sizeof(vis));if(dfs(0,0))break;}printf("Case %d: %d\n", ++kase, maxd);}return 0; }

?

總結

以上是生活随笔為你收集整理的UVA - 11214Guarding the Chessboard守卫棋盘（迭代加深搜索）的全部內容，希望文章能夠幫你解決所遇到的問題。

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