uva11214 Guarding the Chessboard

uva11214 Guarding the Chessboard

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=100945#problem/A

#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MS0(a) memset(a,0,sizeof(a))
#define PII pair<int,int>

using namespace std;

typedef long long ll;
const int maxn=1000100;
const int INF=(1<<29);

int n,m;
char ch[12][12];
int id[12][12];
PII X[maxn];int cnt;
bool put[12][12];

vector<PII> Put(int x,int y)
{
    vector<PII> res;
    REP(i,1,n){
        if(put[i][y]==0){
            put[i][y]=1;
            res.push_back({i,y});
        }
    }
    REP(i,1,m){
        if(put[x][i]==0){
            put[x][i]=1;
            res.push_back({x,i});
        }
    }
    REP(i,1,n){
        int j=x+y-i;
        if(j>=1&&j<=m&&put[i][j]==0){
            put[i][j]=1;res.push_back({i,j});
        }
        j=i-(x-y);
        if(j>=1&&j<=m&&put[i][j]==0){
            put[i][j]=1;res.push_back({i,j});
        }
    }
    return res;
}

void Put_pre(vector<PII> v)
{
    for(int i=0;i<v.size();i++){
        int x=v[i].first,y=v[i].second;
        put[x][y]=0;
    }
}

int Not()
{
    int res=0;
    REP(i,1,cnt){
        int x=X[i].first,y=X[i].second;
        if(put[x][y]==0) res++;
    }
    return res;
}

bool dfs(int x,int y,int cur,int maxd)
{
    int t=(n-1)+(m-1)+2*(min(n,m)-1);
    int tt=Not();
    //cout<<"tt="<<tt<<" cur="<<cur<<" max="<<maxd<<endl;
    if(cur==maxd) return tt==0;
    //cout<<"++"<<endl;
    if((maxd-cur)*t<tt) return 0;
    //cout<<"cur="<<cur<<" maxd="<<maxd<<" x="<<x<<" y="<<y<<endl;
    REP(i,y+1,m){
        //cout<<x<<" "<<i<<endl;
        vector<PII> v=Put(x,i);
        if(dfs(x,i,cur+1,maxd)) return 1;
        Put_pre(v);
    }
    REP(i,x+1,n){
        REP(j,1,m){
            vector<PII> v=Put(i,j);
            if(dfs(i,j,cur+1,maxd)) return 1;
            Put_pre(v);
        }
    }
    return 0;
}

int main()
{
    freopen("in.txt","r",stdin);
    int casen=1;
    while(cin>>n,n){
        cin>>m;
        cnt=0;MS0(id);
        REP(i,1,n){
            REP(j,1,m){
                cin>>ch[i][j];
                if(ch[i][j]=='X') id[i][j]=++cnt,X[cnt]={i,j};
            }
        }
        int ans=INF;
        for(int i=0;;i++){
            //cout<<i<<endl;
            MS0(put);
            if(dfs(1,0,0,i)){
                ans=i;break;
            }
        }
        printf("Case %d: %d
",casen++,ans);

    }
    return 0;
}
/**
题意：
    在n*m的棋盘上放最少的后，使这些后的攻击范围覆盖棋盘上所有标记的格子。
分析：
    IDA*，直接搜即可，最多5个后即可覆盖全部区域，因此最多5层。
类型：
    搜索
注意事项：
    放完后要恢复原状。
坑点：
    似乎并没有。
总结：
    对于比较麻烦或者比较大的题，先想好或者先在纸上写好框架，再写代码效率会更高，避免写到一般重写。
*/