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

1247 阅读 8 评论 0 点赞

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

13 人评分

本文分类：题解列表
浏览次数：1247 次浏览
发布日期：2020-02-16 14:50:53
本文链接：https://blog.dotcpp.com/a/66255

上一篇 > 危险系数DFS处理方法-题解(C++代码)
下一篇 > [编程入门]结构体之成绩统计2-题解(C语言代码)

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

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

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

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

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

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

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

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

评论列表共有 8 条评论

小游 1年前回复TA

@天威难测 这个是深搜

小姜骑猪 2年前回复TA

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;
    }

中南打工人 2年前回复TA

@天威难测 这个就是递归吧

wz 2年前回复TA

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

念念不忘 3年前回复TA

@天威难测 目前来看可有可无https://blog.csdn.net/aastoneaa/article/details/7287733?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522164153819216780271511853%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=164153819216780271511853&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-2-7287733.first_rank_v2_pc_rank_v29&utm_term=int+main%28int+argc%2C+char**+argv%29&spm=1018.2226.3001.4187

天威难测 3年前回复TA

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

天威难测 3年前回复TA

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

Taiga 3年前回复TA

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

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

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

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 8 条评论

发表评论 取消回复

评论列表共有 8 条评论

发表评论取消回复