李华

用户名：2645479600

访问量：18656

签　名：

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

　　自我简介：

欢迎探讨

TA的其他文章

蓝桥杯历届试题-最大子阵-题解(C语言代码)---dp最大子段和思想（详细）
浏览：2096

蓝桥杯2015年第六届真题-切开字符串（C++代码）---substr的简单枚举和map去重
浏览：725

蓝桥杯2015年第六届真题-奇怪的数列（C++代码）---int和char转换的简单应用
浏览：285

你可能喜欢

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

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

　　作者: 李华　　　　发表时间：2020-02-16 14:50:53 浏览：1127　|　评论：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 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

小姜骑猪

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语言程序设计教程（第三版）课后习题7.1 （C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

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

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

Tom数（C语言代码）

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

评论区

精彩推荐

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

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

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

字符串输入输出函数（Java代码）

数列排序（C语言代码）

多输入输出练习1 （C语言代码）

最小公倍数（C语言代码）

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

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

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

李华

TA的其他文章

你可能喜欢

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

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）

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

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

Tom数 （C语言代码）

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

评论区

精彩推荐

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

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

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

字符串输入输出函数 （Java代码）

数列排序 （C语言代码）

多输入输出练习1 （C语言代码）

最小公倍数 （C语言代码）

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

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

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

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

Tom数（C语言代码）

　　评论区

字符串输入输出函数（Java代码）

数列排序（C语言代码）

最小公倍数（C语言代码）