TZOJ 4640：你会做蛋糕吗？

描述

BobLee是个大吃货，喜欢吃好吃的，也喜欢做好吃的。比如做正方形的蛋糕。比如下图这个5*5的蛋糕。

图中的*号是代表BobLee放在上面的草莓。不仅如此，BobLee还喜欢把蛋糕分给自己的好友，比如CMS,YYD,LCM,MCB他们吃。为了好看，分的时候每一块都是正方形的。现在BobLee想知道，能否将一个蛋糕分成几个正方形的小蛋糕（大于等于1个），并且每个蛋糕上面有且仅有一个草莓。

输入

输入第一个为T，代表数据的组数

每组测试数据的第一行是L(0 < L < 20)和N（N > 0），代表一个L*L的蛋糕中有N个草莓

接下来是N行数字，每行是Xi和Yi，代表在（Xi，Yi）处有一个草莓。确保每处最多一个草莓。

输出

如果可以满足要求就输出YES，如果不可以请输出NO

样例输入

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

样例输出

YES

题目来源

2013年武汉科技大学“蓝桥杯”校内选拔赛

题解

一个爆搜题，加上回溯。具体看代码

#include <bits/stdc++.h>
using namespace std;
int l,n;
int mp[25][25];
bool flog;
bool found(int x,int y,int of)//判断这块蛋糕是不是合法的
{
    int mx=x+of;int my=y+of;int s=0;for(int i=x;i<=mx;i++){
    for(int j=y;j<=my;j++){
    if(mp[i][j]){
    s++;if(s>1)  //如果草莓大于1颗就返回0return 0;}else if(mp[i][j]!=0) //如果这块已经被分过了返回0return 0;}}if(s==0)return 0;//如果没有草莓返回0return 1;//合法返回1
}
void cut(int x,int y,int of)//切蛋糕
{
    int mx=x+of;int my=y+of;for(int i=x;i<=mx;i++)for(int j=y;j<=my;j++)mp[i][j]+=2;//将被切蛋糕全部加2
}
bool dfs(int x,int y,int of)
{
    int mx=x+of;int my=y+of;if(!found(x,y,of))//如果不合法直接返回0return 0;cut(x,y,of); //合法就切for(int i=1;i<=l;i++)for(int j=1;j<=l;j++){
    if(mp[i][j]==0||mp[i][j]==1){
    for(int k=0;k<=l-i&&k<=l-j;k++){
    if(dfs(i,j,k)) //继续切return 1;}for(int p=x;p<=mx;p++) //不能切到底就回溯，并返回0{
    for(int q=y;q<=my;q++){
    mp[p][q]-=2;}}return 0; }}return 1; //切完返回1
}
int main()
{
    int t;scanf("%d",&t);while(t--){
    flog=0;memset(mp,0,sizeof(mp));scanf("%d %d",&l,&n);for(int i=0;i<n;i++){
    int x,y;scanf("%d %d",&x,&y);mp[x][y]=1;}for(int i=0;i<l;i++) //从(1,1)为顶点，枚举所以可能边长{
    if(dfs(1,1,i)){
    flog=1;break;}}if(flog)printf("YES\n");else printf("NO\n");}
}