首页 > 搜索 > DFS搜索 > hdu 2589 正方形划分-DFS-[解题报告]C++
2014
02-10

hdu 2589 正方形划分-DFS-[解题报告]C++

正方形划分

问题描述 :

一个边长为L的正方形可以分成 L*L个小正方形. 有N个石子放在 N个小正方形里,能否将它分成 N个 正方形,使得每个正方形里恰有一个石子且这N 个正方形恰好构成整个正方形 .

输入:

输入数据首先包含一个整数T,表示测试实例的个数,然后是T组数据,每组第一行包含2个整数L,N,接下来有N行每行2个整数 r,c,表示第r行c列的小正方形里有一个石子 .1<L<=20;1<N<=L*L; 1<=r,c<=L.

输出:

输入数据首先包含一个整数T,表示测试实例的个数,然后是T组数据,每组第一行包含2个整数L,N,接下来有N行每行2个整数 r,c,表示第r行c列的小正方形里有一个石子 .1<L<=20;1<N<=L*L; 1<=r,c<=L.

样例输入:

3

5 8
2 4
3 3
3 4
3 5
4 2
4 4
4 5
5 5

3 2
1 1
3 3

2 4
1 1
1 2
2 1
2 2

样例输出:

YES
NO
YES

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int map[21][21];
int a[21][21];
bool used[21][21];
int n,m;
bool dfs()
{
    int i,j;
    int x,y,r;
    int flag=0;
    for(i=1;i<=n;i++)
    {
        if(flag) break;
        for(j=1;j<=n;j++)
            if(!used[i][j])
            {
                x=i;y=j;
                flag=1;
                break;
            }
    }
    int x1,y1;
    for(r=0;;r++)
    {
        x1=x+r;y1=y+r;
        if(x1>n||y1>n) break;
        if(a[x1][y1]-a[x1][y-1]-a[x-1][y1]+a[x-1][y-1]>1) break;
        if(a[x1][y1]-a[x1][y-1]-a[x-1][y1]+a[x-1][y-1]==1)
        {
            for(i=x;i<=x1;i++)
                for(j=y;j<=y1;j++)
                    used[i][j]=1;
            if(dfs()) return 1;
            for(i=x;i<=x1;i++)
                for(j=y;j<=y1;j++)
                    used[i][j]=0;
        }
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(!used[i][j])
                return 0;
    return 1;
}
int main()
{
    int cas,x,y;
    scanf("%d",&cas);
    while(cas--)
    {
        memset(map,0,sizeof(map));
        scanf("%d%d",&n,&m);
        while(m--)
        {
            scanf("%d%d",&x,&y);
            map[x][y]=1;
        }
        memset(a,0,sizeof(a));
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+map[i][j];
        memset(used,0,sizeof(used));
        int c=dfs();
        if(c==1) printf("YES\n");
        if(c==0) printf("NO\n");
    }
    return 0;
}

 

解题转自:http://www.cnblogs.com/xuschang-93/archive/2012/04/24/2467512.html


,
  1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.

  2. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环

  3. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1