UVA 11214 Guarding the Chessboard，11214chessboard

UVA 11214 Guarding the Chessboard，11214chessboard

題意：

　　皇後防御的范圍是他所在橫、豎、對角線，地圖上的#為可以放旗子的地方。問最少放幾個皇後能防守所有#。

分析：

　　vis數組開4維，對應行、列、主對角線、副對角線

代碼：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int map[15][15];
int vis[4][30];
int n,m;
int maxn;
int kase;
int same()//判斷是否能防守所有#
{
    int i,j,k;
    for(i=0;i<n;i++)
        for(j=0;j<m;j++)
            if(map[i][j]&&!vis[0][i]&&!vis[1][j]&&!vis[2][i+j]&&!vis[3][n+j-i])
                return 0;
    return 1;
}
int dfs(int d,int cur,int l)//d代表放第幾個皇後，cur代表皇後放在那，cur/m為橫坐標，cur%m為縱坐標，l代表總共有幾個皇後。
{
    int i,j,k;
    if(d==l)
    {
        if(same())
        {
            printf("Case %d: %d\n",++kase,d);
            return 1;
        }
        return 0;
    }
    else
    {
        for(i=cur;i<n*m;i++)
        {
            int x=i/m,y=i%m;
            int tmp1=vis[0][x],tmp2=vis[1][y],tmp3=vis[2][x+y],tmp4=vis[3][n-x+y];
            vis[0][x]=vis[1][y]=vis[2][x+y]=vis[3][n-x+y]=1;
            if(dfs(d+1,i,l))
                return 1;
            vis[0][x]=tmp1,vis[1][y]=tmp2,vis[2][x+y]=tmp3,vis[3][n-x+y]=tmp4;
        }
    }
    return 0;
}
int main()
{
    kase=0;
    while(scanf("%d",&n),n)
    {
        scanf("%d",&m);
        int i,j;
        
        memset(vis,0,sizeof(vis));
        memset(map,0,sizeof(map));
        string s;
        for(i=0;i<n;i++)
        {
            cin>>s;
            for(j=0;j<m;j++)
            {
                if(s[j]=='X')
                    map[i][j]=1;
            }
        }
        for(maxn=0;;maxn++)
        {
            memset(vis,0,sizeof(vis));
            if(dfs(0,0,maxn))
            {
                break;
            }
        }
    }
}