UVA11214 Guarding the Chessboard 题解

题目链接：UVA11214 Guarding the Chessboard

题意：

多组数据。输入一个 \(n×m\) 的棋盘（ \(n,m<10\) ），某些格子有标记。

用最少的皇后守卫（即占据或者攻击）所有带标记的格子。

显然是搜索，这道题的特点在于搜索的深度可能及其大，所以我们需要用迭代加深搜索 (IDA star)。

所谓迭代加深搜索，就是限制一个搜索深度的上限，在本题中我们可以限制放的棋子数量。

因为 \(8\times 8\) 的棋盘都只需要 \(5\) 个皇后，所以实际运行的效率还是比较高的。

时间复杂度 \(\mathcal{O}(\text{ok})\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(15))

char s[N],g[N][N],vis[4][N * 2 + 15];
int n,m,cases,mxdep;
void init() { memset(vis, 0, sizeof(vis)); }
bool check()
{
    for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) {
        if(g[i][j]&&!vis[0][i]&&!vis[1][j]&&!vis[2][i+j]&&!vis[3][i-j+N])
            return false;
    }
    return true;
}
bool dfs(int x,int y,int dep)
{
    if(dep == mxdep) return check();
    for(int a,b,c,d; x <= n; ++x, y = 1) {
        for(; y <= m; y++)
        {
            a = vis[0][x], b = vis[1][y], c = vis[2][x + y], d = vis[3][x - y + N];
            vis[0][x] = vis[1][y] = vis[2][x + y] = vis[3][x - y + N] = 1;
            if(dfs(x, y+1, dep + 1)) return true;
            vis[0][x] = a, vis[1][y] = b, vis[2][x + y] = c, vis[3][x - y + N] = d;
        }
    }
    return false;
}
void solve()
{
    for(int i = 1; i <= n; i++)
    {
        cin >> (s + 1);
        for(int j = 1; j <= m; j++) g[i][j] = (s[j] == 'X');
    }
    for(mxdep = 0; ; ++mxdep) if(init(), dfs(1,1,0)) break;
    cout << "Case " << ++cases << ": " << mxdep << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    while(cin >> n >> m, n) solve();
    return 0;
}