zoj2479 Cover the Rectangular Ground

肯定是dfs搜一下的，但是呢存在一个很大的剪枝，也就是面积必定要是相等的，那么如何去操作呢，可以想到的是二进制枚举选取的方法，然后把方法中选取的矩形面积求和并判断一下即可，然后dfs搜索，要注意的是，需要维持现状的变量在变化之前一定要记录，要变回来时，一定要变回来，另外在dfs中还可以判断覆盖是否合理，以及是否已经没有可找到的空白区域。

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<string>

#include<set>

#include<algorithm>

#include<vector>

#include<queue>

#include<list>

#include<cmath>

#include<cstring>

#include<map>

#include<stack>

using namespace std;

#define INF 0x3f3f3f3f

#define maxn 2005

#define ull unsigned long long

#define ll long long

#define hashmod 99999839

#define mod 9997

int T,n,m,q,x[],y[],p[],sx,sy,b;

int a[][];

bool f[],ans;

bool overlap(int i,int v,int t){

    int ex = x[i],ey = y[i];

    if(v) swap(ex,ey);

    if(sx + ex -  >= n || sy + ey -  >= m) return false;

    for(int j = sx;j < sx + ex;++j){

        for(int k = sy;k < sy + ey;++k){

            if(t && a[j][k]) return false;

        }

    }

    for(int j = sx;j < sx + ex;++j){

        for(int k = sy;k < sy + ey;++k){

            a[j][k] = t;

        }

    }

    return true;

}

bool findempty(){

    for(int i = sx;i < n;++i){

        for(int j = ;j < m;++j){

            if(!a[i][j]){

                sx = i,sy = j;

                return true;

            }

        }

    }

    return false;

}

bool check(){

    for(int i = ;i < n;++i){

        for(int j = ;j < m;++j){

            if(!a[i][j]) return false;

        }

    }

    return true;

}

void dfs(){

    bool flag = false;

    for(int i = ;i < q;++i){

        if((b & p[i]) && !f[i]){

            flag = true;

            f[i] = true;

            int tx = sx,ty = sy;

            if(overlap(i,,)){

                if(findempty()) dfs();

                else{

                    ans = true;

                    return;

                }

                if(ans) return;

                sx = tx,sy = ty;

                overlap(i,,);

            }

            if(!overlap(i,,)){

                f[i] = false;

                continue;

            }

            if(findempty()) dfs();

            else{

                ans = true;

                return;

            }

            if(ans) return;

            sx = tx,sy = ty;

            overlap(i,,);

            f[i] = false;

        }

    }

    if(!flag && check()) ans = true;

}

bool solve(){

    for(int i = ;i < p[q];++i){//枚举选取哪一些

        int s = ;

        for(int j = ;j < q;++j){

            if(i & p[j]) s = s + x[j] * y[j];

        }

        if(s != n * m) continue;

        b = i;

        ans = false;

        sx = sy = ;

        dfs();

        if(ans) return true;

    }

    return false;

}

int main(){

 /*submit failed*/

 /*submit failed*/

 /*submit failed*//*submit failed*//*submit failed*/

    freopen("a.in","r",stdin);

    freopen("b.out","w",stdout);

    cin >> T;

    p[] = ;

    for(int i = ;i <= ;++i) p[i] = p[i - ] << ;

    while(T--){

        scanf("%d%d",&n,&m);

        cin >> q;

        for(int i = ;i < q;++i){

            scanf("%d%d",&x[i],&y[i]);

        }

        memset(a,,sizeof(a));

        memset(f,false,sizeof(f));

        if(solve()) puts("YES");

        else puts("NO");

    }

    return ;

}

巴特西

zoj2479 Cover the Rectangular Ground

最新文章

热门文章