TOJ 4640: 你会做蛋糕吗？深搜回溯

130 阅读 0 评论 86 点赞

我是靠谱客的博主悲凉草丛，这篇文章主要介绍TOJ 4640: 你会做蛋糕吗？深搜回溯，现在分享给大家，希望可以做个参考。

4640: 你会做蛋糕吗？分享至QQ空间
时间限制(普通/Java):1000MS/3000MS 内存限制:65536KByte
总提交: 18 测试通过:9
描述

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 n,m,vis[25][25],flag;
char g[25][25];
void b_vis(int x,int y,int k){ // 标记
    for(int i=x;i<=x+k;i++)
        for(int j=y;j<=y+k;j++)
        vis[i][j]=1;
}
void f_vis(int x,int y,int k){ //回溯标记
    for(int i=x;i<=x+k;i++)
        for(int j=y;j<=y+k;j++)
        vis[i][j]=0;
}
void dfs(int x,int y){
  //  printf("%d %dn",x,y);
    if(flag) return;
    if(y>n||vis[x][y]) dfs(x+1,1); //越界或已被别的蛋糕用了，搜下个点
    if(x>n){ //行越界，表示搜完了
        flag=1;
        return;
    }
    for(int k=0;k<n;k++){ // k代表正方形的边长
        int ans=0;
        if(x+k>n||y+k>n) return; // 越界返回
        for(int i=x;i<=x+k;i++)
        for(int j=y;j<=y+k;j++){
            if(g[i][j]=='*') ++ans;  //计算草莓数量
        }
        if(ans>1) return; //多了返回
        if(ans==1){  //满足 往下走
            b_vis(x,y,k);
            dfs(x,y+k+1);
            f_vis(x,y,k);
        }
    }
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
        scanf("%d%d",&n,&m);
        flag=0;
        memset(vis,0,sizeof vis);
        memset(g,' ',sizeof g);
        for(int i=0;i<m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            g[x][y]='*';
        }
        dfs(1,1);
        printf("%sn",flag?"YES":"NO");
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
using namespace std;
int n,m,vis[25][25],flag;
char g[25][25];
void b_vis(int x,int y,int k){ // 标记
    for(int i=x;i<=x+k;i++)
        for(int j=y;j<=y+k;j++)
        vis[i][j]=1;
}
void f_vis(int x,int y,int k){ //回溯标记
    for(int i=x;i<=x+k;i++)
        for(int j=y;j<=y+k;j++)
        vis[i][j]=0;
}
void dfs(int x,int y){
  //  printf("%d %dn",x,y);
    if(flag) return;
    if(y>n||vis[x][y]) dfs(x+1,1); //越界或已被别的蛋糕用了，搜下个点
    if(x>n){ //行越界，表示搜完了
        flag=1;
        return;
    }
    for(int k=0;k<n;k++){ // k代表正方形的边长
        int ans=0;
        if(x+k>n||y+k>n) return; // 越界返回
        for(int i=x;i<=x+k;i++)
        for(int j=y;j<=y+k;j++){
            if(g[i][j]=='*') ++ans;  //计算草莓数量
        }
        if(ans>1) return; //多了返回
        if(ans==1){  //满足 往下走
            b_vis(x,y,k);
            dfs(x,y+k+1);
            f_vis(x,y,k);
        }
    }
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
        scanf("%d%d",&n,&m);
        flag=0;
        memset(vis,0,sizeof vis);
        memset(g,' ',sizeof g);
        for(int i=0;i<m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            g[x][y]='*';
        }
        dfs(1,1);
        printf("%sn",flag?"YES":"NO");
	}
}