李华

用户名：2645479600

访问量：17664

签　名：

等　　级
排　　名	469
经　　验	4570
参赛次数	2
文章发表	22
年　　龄	22
在职情况	学生
学　　校	华软、江理
专　　业	电信、计算机

　　自我简介：

欢迎探讨

TA的其他文章

蓝桥杯剪格子-题解(C语言代码)-----初学者可以看看，详细带图（dfs）
浏览：1063

[2013年第四届真题]危险系数-题解(C++代码)------STL，dfs
浏览：889

蓝桥杯历届试题-国王的烦恼-题解(C语言 with STL)---参考啊哈算法,文字解释详细
浏览：1405

你可能喜欢

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

【明明的随机数】（C++代码）（C++库中有qsort函数直接快排，不用码排序代码hhh）

蓝桥杯剪格子-题解(C语言代码)-----初学者可以看看，详细带图（dfs）

　　作者: 李华　　　　发表时间：2020-02-16 14:50:53 浏览：1063　|　评论：5　

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

解题思想:
1.题目要求最后的答案要包含左上角格子，所以直接拿左上角格子作为起点进行深度优先搜索
2.解题步骤:
首先我们分析样例是怎么做的:
①从第零行零列的元素作为起点深搜,每个点进行上下左右判断，寻找哪个方向可以走。以图中第一个点"10"为例，首先判断上面,上面不能走;于是判断左面,左面不能走;再判断下面能不能走，发现下面可以走了就往下走。每走一步就标记原本的地方再往下走，所以我们将“10”这个点标记起来，再以“20”这个点为基准继续递归。接着，“20”的上面不能走，因为不能走回头路啊，“10”被标记过了，所以我们判断左面，左面不能走，再判断下面.......以此类推
（判断能不能走的标准:1.不能越出地图 2.即将要走下去的点没有被标记）
3.每走一步，就计算走过的点的和是多少，再计算没走过的点的和是多少。如果两个和相等，就代表符合条件，我们尝试是否可以更新result，如果走过的格子数比result小，就可以更新。
4.每次递归完记得将标记全部清除。不知道为什么的话，举个例子，以“20”这个点为例子，我们以“20”下面的格子进行深搜，下面这个方向深度搜索完了，那这个地图很多的格子就都被标记了啊，那我们一会还要尝试“20”的右边，发现格子都被标记过了，那右边就没有办法尝试了。

注意事项:你输入的时候是m，n的顺序，但是题目说的是n行m列，很容易出错
![](/image_editor_upload/20200303071107_75668.png)
```c
#include <stdio.h>
int a[10][10];
int flag[10][10];
int result=10000000;
int m,n;
int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}};//用于记录四个方向的x,y变化(上左下右) 
int in(int x,int y)
{
	if(x>=0 && x<n && y>=0 && y<m)	return 1;
	else	return 0;
}
void dfs(int x,int y,int sum)	//x,y记录坐标,sum记录走到这步的和 
{
	sum=sum+a[x][y];
	flag[x][y]=1;
	int sum_other=0;	//用于记录另一部分的和 
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(flag[i][j]==0)	//0代表没有走过的点 
			sum_other=sum_other+a[i][j];
		}
	} 
	if(sum_other==sum)
	{
		int num=0;	//计算被标记的格子数 
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				if(flag[i][j]==1)	num++;
			}
		}
		if(num<result)	result=num;
		return;
	}
	for(int i=0;i<4;i++)
	{
		int tx=x+dir[i][0];
		int ty=y+dir[i][1];
		if(in(tx,ty)&&flag[tx][ty]==0)
		{
			dfs(tx,ty,sum);
		}
	}
	flag[x][y]=0;	//四个方向全部遍历完都没有解,那么取消标记 
}
int main(int argc, char** argv)
{
	scanf("%d %d",&m,&n);
	for(int i=0;i<n;i++)	//n行m列 
	{
		for(int j=0;j<m;j++)
		{
			scanf("%d",&a[i][j]);
		}
	}
	dfs(0,0,0);
	printf("%d",result);
	return 0;
}
```

0.0分

16 人评分

C语言网推出会员服务，提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源，享受丰富的技术学习到变现的乐趣，以含金量和学习效果勇敢挑战同类辅导！点击了解开通

　　评论区

小姜骑猪

if(sum_other==sum)
    {
        int num=0;    //计算被标记的格子数 
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(flag[i][j]==1)    num++;
            }
        }
        if(num<result)    result=num;//为什么这里要判断一下，我写的代码这里没有判断就会结果不对
        return;
    }

2022-07-06 10:28:21

代码写的很棒,注释清晰,深搜的格式也很规范,思路明确!!!

2022-04-02 15:01:00

天威难测

我还有个问题哦，这个main函数括号里的是啥玩意儿呀

2021-02-05 03:17:34

天威难测

我在想能不能采用递归的方式呀，当然只是个想法，我暂时实现不了

2021-02-05 01:41:20

Taiga

可是，没有看到判断支路的解释：
比如：
20  20  10
20  10  10
10  10  10
按照题主的描述：只是一条龙查询的

2021-02-02 17:08:24

李华

TA的其他文章

你可能喜欢

数字整除（C语言代码）

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

【明明的随机数】（C++代码）（C++库中有qsort函数直接快排，不用码排序代码hhh）

C二级辅导-等差数列（C语言代码）

十->二进制转换（C++代码）（零和负数需要特殊处理）

蓝桥杯剪格子-题解(C语言代码)-----初学者可以看看，详细带图（dfs）

评论区

精彩推荐

C二级辅导-求偶数和（C语言代码）

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

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

C语言考试练习题_排列（C语言代码）

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

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

Hello, world! （C语言代码）

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

A+B for Input-Output Practice (VI) （C语言代码）

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

李华

TA的其他文章

你可能喜欢

数字整除 （C语言代码）

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

【明明的随机数】 （C++代码）（C++库中有qsort函数直接快排，不用码排序代码hhh）

C二级辅导-等差数列 （C语言代码）

十->二进制转换 （C++代码）（零和负数需要特殊处理）

蓝桥杯剪格子-题解(C语言代码)-----初学者可以看看，详细带图（dfs）

评论区

精彩推荐

C二级辅导-求偶数和 （C语言代码）

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

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

C语言考试练习题_排列 （C语言代码）

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

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

Hello, world! （C语言代码）

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

A+B for Input-Output Practice (VI) （C语言代码）

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

数字整除（C语言代码）

【明明的随机数】（C++代码）（C++库中有qsort函数直接快排，不用码排序代码hhh）

C二级辅导-等差数列（C语言代码）

十->二进制转换（C++代码）（零和负数需要特殊处理）

　　评论区

C二级辅导-求偶数和（C语言代码）

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

C语言考试练习题_排列（C语言代码）