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

1579 阅读 11 评论 0 点赞

原题链接：蓝桥杯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 人评分

本文分类：题解列表
浏览次数：1579 次浏览
发布日期：2020-02-15 20:53:00
本文链接：https://blog.dotcpp.com/a/66221

上一篇 > 蓝桥杯算法提高VIP-数组输出-题解(Java代码)
下一篇 > 蓝桥杯算法提高VIP-最小乘积(提高型)-题解(Java代码)

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表共有 11 条评论

romanticroom 2月前回复TA

错了

dotcpp0660183 11月前回复TA

这题是错题，无论是什么题解基本上都很难是完美的
输入
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

余生 1年前回复TA

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

职业摆烂人 2年前回复TA

@三个月仅可修改一次 （0,0）和（1,0）一组，其余的一组不是可以的吗

三个月仅可修改一次 2年前回复TA

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

Today 3年前回复TA

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

我讨厌起名字 4年前回复TA

@SavenNeer 那有没有啥更好的算法来解决这道题目

SavenNeer 4年前回复TA

@SavenNeer 好像有歧义，我是说我所引用的博主的那段话分析的并不错

SavenNeer 4年前回复TA

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

我讨厌起名字 4年前回复TA

@码是真不 hhh我也错了，查了好久才发现

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

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 11 条评论

发表评论 取消回复

评论列表共有 11 条评论

发表评论取消回复