11214 - Guarding the Chessboard（暴力搜索）

11214 - Guarding the Chessboard（暴力搜索）

IDA*算法， 從小到大枚舉深度上限，不過該題是有深度上限的，題目中的第一個樣例表明：最多需要5個皇後就可以覆蓋整個棋盤 。

利用紫書上的技巧，我們可以快速的判斷任意兩個棋子是不是在同一行、同一列、同一對角線 （詳情見紫書P193那兩個圖）。

這樣之後暴力搜索就可以了 。 每一層需要O（nm）的復雜度，但是實際上並不需要那麼大的復雜度 。和八皇後問題類似 ， 當前行之前的行已經放置了皇後，所以不必在管，每次從下一行開始放置就好 。

細節見代碼：

#include
using namespace std;
int n,m,maxd,kase = 0,vis[10][30];
char s[15][15];
bool dfs(int cur,int r) {
    if(cur == maxd) {
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++)
                if(s[i][j] == 'X' && !vis[0][i] && !vis[1][j] && !vis[2][i+j] && !vis[3][i-j+11]) return false;
        }
        return true;
    }
    for(int i=r;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            if(!vis[0][i] || !vis[1][j] ||!vis[2][i+j] ||!vis[3][i-j+11]) {
                int v1 = vis[0][i], v2 = vis[1][j], v3 = vis[2][i+j], v4 = vis[3][i-j+11];//注意，一定要恢復“原樣”
                vis[0][i] = vis[1][j] = vis[2][i+j] = vis[3][i-j+11] = 1;
                if(dfs(cur+1,i+1)) return true;
                vis[0][i] = v1; vis[1][j] = v2; vis[2][i+j] = v3; vis[3][i-j+11] = v4;
            }
        }
    }
    return false;
}
int main() {
    while(~scanf(%d,&n)&&n) {
        scanf(%d,&m);
        for(int i=1;i<=n;i++) scanf(%s,s[i]+1);
        for(maxd = 1; maxd < 5 ; ++maxd) {
            memset(vis,0,sizeof(vis));
            if(dfs(0,0)) break;
        }
        printf(Case %d: %d
,++kase,maxd);
    }
    return 0;
}