国际大学生程序设计竞赛例题_5.11美味的蛋糕

1,题意:输入矩阵维数n,枣的个数m
2,输出:是否可以将矩阵分成m个方阵,每个方阵含有一个枣.
3.解答:
向下向右扩展,注意一个枣的情况需要回溯.
4,实现代码

#include <iostream>
using namespace std;

#define NUM 100
int cnt; //测试数目
int n;//矩阵维数
int m;//枣的个数

bool isMark[NUM][NUM];
bool isCase[NUM][NUM];

int getNum(int x1,int y1,int x2,int y2)
{
    int sum=0;
    for(int i=x1;i<=x2;i++)
        for(int j=y1;j<=y2;j++)
            if(isCase[i][j])
                sum++;
    return sum;
}

int fill(int x,int y)
{
    if(x>n-1)
    {
        x=0;
        y++;
        if(y>n-1)
            return 1;
    }

    //下右方向寻找第一个没有被切割的点
    while(isMark[x][y])
    {
        if(x++==n-1)
        {
            x=0;
            if(y++==n-1) return 1;
        }
    }

    //向右下方遍历
    for(int k=0; k+x<n&&k+y<n; k++)
    {
        if( getNum(x,y,x+k,y+k) > 1 ) break;
        if( getNum(x,y,x+k,y+k) == 0 ) continue;
        if( getNum(x,y,x+k,y+k) == 1 )
        {
            for(int i=x;i<=x+k;i++)
                for(int j=y;j<=y+k;j++)
                    isMark[i][j]=true;
            if(fill(x+1,y)) return 1;
            //回溯,继续往下扩展
            for(int i=x;i<=x+k;i++)
                for(int j=y;j<=y+k;j++)
                    isMark[i][j]=false;
        }
    }
    return 0;
}

int main()
{
    freopen("5.11.in","r",stdin);
    cin>>cnt;
    int x,y;
    while(cnt--)
    {
        cin>>n>>m;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
            {
                isMark[i][j]=false;
                isCase[i][j]=false;
            }
        while(m--)
        {
            cin>>x>>y;
            x--,y--;
            isCase[x][y]=true;
        }
        if(fill(0,0))
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }

    return 0;
}