hdu 4462 Scaring the Birds(暴力、細読)

タイトル:http://acm.hdu.edu.cn/showproblem.php?pid=4462
私が言いたいのは、この問題はデータ構造や複雑なアルゴリズムを試すのではなく、人の読書能力と思考の緻密さを試すことだ.2つあります:第1点はすべて見ることができて、k=0の時に既存の作物を保護することができません;第2点は、k=n*nのとき、すなわち、すべての点が作物を持たず、直接0を出力する.

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,k;   //2^16=65536
bool tag[55][55];
int sec[11][2],r[11];
bool chao(int a,int b){
    return (a<1||a>n||b<1||b>n);
}
void cover(int x,int y,int r){
    for(int j=y-r;j<=y+r;j++){
        if(chao(x,j))continue;
        tag[x][j]=1;
    }
    for(int i=x-r;i<x;i++){
        for(int j=y;j<=y+i-x+r;j++){
            if(chao(i,j));
            else tag[i][j]=1;
            if(chao(2*x-i,j));
            else tag[2*x-i][j]=1;
            if(chao(i,y-(j-y)));
            else tag[i][2*y-j]=1;
            if(chao(2*x-i,2*y-j));
            else tag[2*x-i][2*y-j]=1;
        }
    }
}
bool ok(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(tag[i][j]==0)return 0;
        }
    }
    return 1;
}
void showtag(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)cout<<tag[i][j]<<" ";
        cout<<endl;
    }
}
void intial(){
    for(int i=1;i<=k;i++){
        tag[sec[i][0]][sec[i][1]]=1;
    }
}
int main()
{
    //freopen("cin.txt","r",stdin);
    while(cin>>n&&n){
        scanf("%d",&k);
        memset(sec,0,sizeof(sec));
        memset(r,0,sizeof(r));
        for(int i=1;i<=k;i++)scanf("%d%d",&sec[i][0],&sec[i][1]);
        for(int i=1;i<=k;i++)scanf("%d",&r[i]);
        int length=1<<k,ans=0x3f3f3f3f;
        for(int i=0;i<length;i++){
            memset(tag,0,sizeof(tag));
            intial();
            //showtag();
            if(ok()){
                ans=0;
                break;
            }
            int sum=0;
            for(int j=1;j<=k;j++){
                if((i>>(j-1))&1){
                    sum++;
                    cover(sec[j][0],sec[j][1],r[j]);
                }
            }

            //cout<<"sum: "<<sum<<endl;
            if(ok())ans=ans<sum?ans:sum;
        }
        if(ans>k)printf("-1
");
        else printf("%d
",ans);
    }
    return 0;
}