首页 > 代码库 > UVa11214 Guarding the Chessboard (IDA*)
UVa11214 Guarding the Chessboard (IDA*)
链接：http://vjudge.net/problem/23958
分析：控制最大递归深度为maxd，也就是枚举个数maxd个皇后守卫的时候，dfs以行枚举放皇后守卫的位置，确保放皇后守卫的位置的行，列，主和副对角线上没有其它守卫，否则就不是最优的了，每次递归从上次放的行的下一行开始放，放满maxd个后进行判断是否所有标记格子都被攻击到。是则直接返回true输出最少守卫，否则返回递归上一层继续枚举，vis要复位。
1 #include <cstdio> 2 #include <cstring> 3 4 const int maxn = 11; 5 6 int n, m, maxd; 7 char G[maxn][maxn]; 8 bool vis[4][maxn << 1]; 9 10 bool dfs(int cur, int d) {11 if (d == maxd) {12 for (int i = 1; i <= n; i++)13 for (int j = 1; j <= m; j++)14 if (G[i][j] == ‘X‘ && !vis[0][i] && !vis[1][j] && !vis[2][j - i + n] && !vis[3][i + j])15 return false;16 return true;17 }18 for (int i = cur; i <= n; i++)19 for (int j = 1; j <= m; j++) {20 if (!vis[0][i] || !vis[1][j] || !vis[2][j - i + n] || !vis[3][i + j]) {21 bool br = vis[0][i], bc = vis[1][j], bm = vis[2][j - i + n], bd = vis[3][i + j];22 vis[0][i] = vis[1][j] = vis[2][j - i + n] = vis[3][i + j] = true;23 if (dfs(cur + 1, d + 1)) return true;24 vis[0][i] = br, vis[1][j] = bc, vis[2][j - i + n] = bm, vis[3][i + j] = bd;25 }26 }27 return false;28 }29 30 int main() {31 int kase = 0;32 while (scanf("%d%d", &n, &m) == 2 && n) {33 for (int i = 1; i <= n; i++) scanf("%s", G[i] + 1);34 for (maxd = 0; ; maxd++) {35 memset(vis, 0, sizeof(vis));36 if (dfs(1, 0)) break;37 }38 printf("Case %d: %d\n", ++kase, maxd);39 }40 return 0;41 }
UVa11214 Guarding the Chessboard (IDA*)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。