我讨厌起名字

用户名：jeffrey222

访问量：7603

签　名：

等　　级
排　　名	6665
经　　验	1332
参赛次数	1
文章发表	8
年　　龄	0
在职情况	学生
学　　校	合工大
专　　业	信息计

　　自我简介：

编程小菜鸡

TA的其他文章

分糖果-通俗的方法(C++代码)
浏览：1072

剪格子-DFS+迭代加深搜索(C++描述，错25%的进来看)
浏览：1255

危险系数DFS处理方法-题解(C++代码)
浏览：765

你可能喜欢

剪格子-DFS+迭代加深搜索(C++描述，错25%的进来看)

　　作者: 我讨厌起名字　　　　发表时间：2020-02-15 20:53:00 浏览：1255　|　评论：6　

原题链接：蓝桥杯2013年第四届真题-剪格子

##### 分析
- 首先要注意的是，题目输入的是先输m再输n，但是是**n行m列的**，一定要看清楚要求的问题！那些错误25%的代码问题大都在这。

- 对于该问题，首先对所有数据求和，最后问题变为寻找到一块连在一块的数据之和等于所有数据的一半即可。典型的dfs问题，记得回溯。

- 那么怎么求最少格子数呢，我的思路是先从(0,0)开始，假设答案为1，若不可，将答案+1，继续尝试。因为本题解答树深度不会超过100，所以一定能在有限的深度里找到答案。

- 接下来是非常非常重要的一点，大家看一下这组数据：
						5  10   15
						7   1   2
						3   3   34
其实答案应该为5(左边加上边)，这块数据被(0，0)点分割成两块，dfs无法探索出这样的路径，可再写一个函数用于这种特殊情况的判断，只需maxd-2次判断即可。但由于蓝桥和该网站的数据不够全面，未考虑到这种情况的代码也是正确的，所以我也未完善自己的代码，主要是因为菜和懒。

------------

##### 代码
```cpp
#include<iostream>
#include<cstring>
#define N 100
using namespace std;

int board[N+5],m,n; //n行m列 
int vis[N+5];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int solve_sum=0;

int sum(int a[],int n)  //求和函数 
{
	int i,sum=0;
	for(i=0;i<n;++i) sum+=a[i];
	return sum;
}

//从(m1,n1)开始探索k步，如果达到goal，则返回ture 
bool solve(int goal,int m1,int n1,int k){
	int i = m1*m + n1;
	int j;
	solve_sum += board[i];
	vis[i]=1;
	if(solve_sum == goal) 	return true;
	if(k==0 || solve_sum>goal)	return false; //剪枝 
	for(j=0;j<4;++j){ //未达目标或未走完 
		int idx=(m1+dx[j])*m + n1+dy[j];
		if(m1+dx[j]>-1 && m1+dx[j]<n
		            && n1+dy[j]>-1 && n1+dy[j]<m && !vis[idx])
		{
			if(solve(goal,m1+dx[j],n1+dy[j],k-1))	return true;
			vis[idx] = 0;
			solve_sum -= board[idx];
		}
	}
	return false;
}

int main()
{
	int i,maxd=1;
	cin>>m>>n;
	for(i=0;i<m*n;++i)	cin>>board[i];
	int s,goal;
	s=sum(board,m*n);
	if(s&1)	  cout<<0;  //奇数一定无法分割
	else{
		goal = s/2;
		while(maxd<m*n){ //主循环 
			memset(vis,0,sizeof(vis));
			if(solve(goal,0,0,maxd-1)){
				cout<<maxd;
				break;
			}
			maxd++;
			solve_sum=0; //清零 
		}
	}
	if(maxd==m*n)  cout<<0; //未找到 
	return 0;
} 
```

0.0分

9 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

　　评论区

dotcpp0660183

这题是错题，无论是什么题解基本上都很难是完美的
输入
3 3
1 1 1
8 1 1
1 1 1
输出8

输入
4 3
2 2 2 2
2 2 9 2
2 2 2 11
输出0
hack

2024-02-01 18:46:02

余生

在深度为多少时，用dfs会报错？

2023-01-26 09:51:37

三个月仅可修改一次

DFS本质上只能解决S型连通问题，不能解决T型连通问题，如果存在解法
1 0 0 
1 1 0
1 0 0
那么用DFS是无法得到的，由于本题数据垃圾，不存在卡这种解法的数据

2022-04-02 10:52:22

Today

嗷嗷~确实审题好……膜拜！！！

2021-02-14 01:46:11

SavenNeer

其实答案应该为5(左边加上边)，这块数据被(0，0)点分割成两块，dfs无法探索出这样的路径，可再写一个函数用于这种特殊情况的判断，只需maxd-2次判断即可。但由于蓝桥和该网站的数据不够全面，未考虑到这种情况的代码也是正确的，所以我也未完善自己的代码，主要是因为菜和懒。
上面这段话是这道题目的最大的漏洞，也是DFS在图论搜索中的一大特点。DFS在某一个分支形成的图一定是可以一笔画的。而对于不能够在图上一笔画的某一分支，则对于DFS搜索则是难以实现。

2020-03-07 14:25:26

码是真不

哈哈 审题又没注意

2020-02-25 11:29:14

我讨厌起名字

TA的其他文章

你可能喜欢

一个简单易懂的代码

输出九九乘法表（C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C++代码）

剔除相关数（C语言代码）

点我有惊喜！你懂得！

剪格子-DFS+迭代加深搜索(C++描述，错25%的进来看)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）scanf后面加个getchar（），收掉回车符，就可以用gets了

小九九（C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

简单的a+b （C语言代码）

C语言训练-数字母（C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

蓝桥杯历届试题-翻硬币（C++代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

数组输出（C语言代码）

我讨厌起名字

TA的其他文章

你可能喜欢

一个简单易懂的代码

输出九九乘法表 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C++代码）

剔除相关数 （C语言代码）

点我有惊喜！你懂得！

剪格子-DFS+迭代加深搜索(C++描述，错25%的进来看)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）scanf后面加个getchar（），收掉回车符，就可以用gets了

小九九 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

简单的a+b （C语言代码）

C语言训练-数字母 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

蓝桥杯历届试题-翻硬币 （C++代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

数组输出 （C语言代码）

输出九九乘法表（C语言代码）

剔除相关数（C语言代码）

　　评论区

小九九（C语言代码）

C语言训练-数字母（C语言代码）

蓝桥杯历届试题-翻硬币（C++代码）

数组输出（C语言代码）