題目：Guarding the Chessboard

題意：一個n*m的矩陣上有一堆敵人X，最少放置幾個皇后可全部消滅。

思路：

（1）枚舉：枚舉矩陣中的每一個位置，用當前index/m 和 index%m 得出 橫縱坐標。

（2）標記：同八皇后問題一樣，也是標記行，列，對角線。但這個標記不是用于當前是否此點放沒放皇后，而是用于檢測敵人是否被消滅了。而且，這里沒枚舉到一個位置時，先將此位置的標記預先繼續下來，然后再標記。最后再還原。還原的時候不是直接賦值0，因為有可能不一樣，所以要預先記錄下來。

（3）判斷：遍歷整個矩陣中的X位置，看X位置的標記數組是否都標記了，如果都標記了說明皇后都攻擊到了，否則沒有。

（4）迭代皇后數量，一旦成功，即為最少！

思維一定要開闊，我開始想的是每次看消滅了的敵人數。其實就是利用八皇后的標記，看敵人是否在標記范圍內就判斷了?。。∵€有就是標記不是都永遠是一個套路  ，本題就是標記數組有變化，需要預先保存后還原！

參考：專攻挖掘機炒雞蛋算法博客

代碼：

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int maxn = 15;char g[maxn][maxn];int visit[4][maxn*3];int n,m,cnt,maxd;inline bool success(){//尋找每個X障礙物所對應的行，列和對角線是否被標記過    for(int i=0;i<n;i++)        for(int j=0;j<m;j++)            if(g[i][j] == 'X' && !visit[0][i] && !visit[1][j] && !visit[2][i+j] && !visit[3][i-j+maxn]) return false;    return true;}bool dfs(int index,int d){    if(success()) return true;    if(d == maxd) return false;    for(int pos=index;pos < n*m;pos++){//枚舉橫縱坐標        int i = pos/m , j = pos%m,save[4];//注意save不能設置全局        save[0] = visit[0][i];save[1] = visit[1][j];save[2] = visit[2][i+j];save[3] = visit[3][i-j+maxn];//將此點之前的標記記錄        visit[0][i] = visit[1][j] = visit[2][i+j] = visit[3][i-j+maxn] = 1;//標記此點        if(dfs(pos,d+1)) return true;        visit[0][i] = save[0];visit[1][j] = save[1];visit[2][i+j] = save[2];visit[3][i-j+maxn] = save[3];//還原    }    return false;}inline int solve(){//枚舉深度即最少皇后    for(maxd=0;maxd<6;maxd++){        memset(visit,0,sizeof(visit));        if(dfs(0,0)) return maxd;    }    return 5;//最大為5}int main(){    int kcase = 1;    while(scanf("%d",&n)!=EOF && n){        scanf("%d",&m);        for(int i=0;i<n;i++) scanf("%s",g[i]);        PRintf("Case %d: %d/n",kcase++,solve());    }    return 0;}