计科余定成

用户名：dotcpp0598358

访问量：15792

签　名：

孙蕾，我好喜欢你啊，为了你我要把键盘敲烂!!!

等　　级
排　　名	41
经　　验	13047
参赛次数	1
文章发表	69
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

我是余定成

TA的其他文章

刻录光盘（c++）
浏览：66

你可能喜欢

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

围成面积（搜索）

　　作者: 计科余定成　　　　发表时间：2023-02-16 18:01:00 浏览：145　|　评论：0　

原题链接：围成面积

解题思路：这道题可以使用深度优先搜索（DFS）来解决。
`1.遍历图形`
——`首先，我们需要遍历给定的图形，找出所有未被围住的点。为了确保我们不会遗漏任何一个未被围住的点，我们需要从图形的边缘开始遍历，即从图形的四个边界开始，沿着边界向内扩展，直到遇到被围住的点或图形的内部边界。在这个过程中，我们需要使用递归算法，以确保能够遍历到图形中的所有点。`
——`具体来说，我们可以假设图形的大小为 N*N，将其扩展为 (N+2)*（N+2) 的大小，即在图形周围添加一圈宽度为 1 的区域。这样，我们就可以从外向内遍历图形，从 (0,0) 开始，依次遍历每个点，如果当前点是边缘上的点且其值为 0，则将其标记为 1，表示它不是被围住的点，然后继续向四周扩展。如果当前点是被围住的点或者已经被标记过，或者超出了图形的范围，则直接返回，不再继续扩展。`
`2.统计围成面积`
——`在完成图形的遍历之后，我们可以统计未被标记的点的个数，这些点就是被围住的点。由于我们已经在遍历过程中标记了所有不是被围住的点，所以这个过程非常简单，只需要遍历整个图形，统计未被标记的点的个数即可。`
注意事项：
```cpp
坐标的范围：在本题中，给定的是一个 10x10 的图形，但是要计算围成的面积，需要在周围围上一圈，即将图形大小扩展到 12x12，以便能够从外部遍历。同时，需要注意数组下标越界的问题，要保证所有的坐标在 0 到 11 之间。
遍历方式：本题需要从外部遍历，以保证围成的区域都能被标记。一般来说，深度优先遍历（DFS）和广度优先遍历（BFS）都可以解决此类问题，选择哪种方式可以根据个人喜好或实际情况来决定。
标记方式：在遍历过程中，需要将所有能够到达的点都标记为已访问过，以便最后计算未被标记的点数。本题中可以用二维数组来表示点的访问状态，0 表示未访问过，1 表示已访问过。在遍历过程中，遇到已经访问过的点或者超出边界的点，需要直接返回，否则会出现死循环或者越界的问题。
统计面积：最后需要统计围成的面积，即未被标记的点数。这可以通过遍历整个数组，计算未被标记的点的个数来实现。
```
参考代码：
```cpp
#include<bits/stdc++.h>
using namespace std;

const int N = 12;
// 图形大小为 12x12，因为需要在外围加一圈障碍物
int mp[N][N]; // 存储图形

int dx[4] = {1, -1, 0, 0}; // 增量数组
int dy[4] = {0, 0, 1, -1};

// 深度优先搜索算法
void dfs(int x, int y) {
	// 判断是否越界或者当前点已经被访问过或者当前点是障碍物
	if (x < 0 || y < 0 || x >= N || y >= N || mp[x][y] == 1) return;
	// 标记当前点为已经访问过
	mp[x][y] = 1;
	// 对当前点的四个相邻点进行 DFS 遍历
	for (int i = 0; i < 4; i++) {
		int tx = x + dx[i];
		int ty = y + dy[i];
		dfs(tx, ty);
	}
}

int main() {
	// 读入图形
	for (int i = 1; i <= 10; i++) {
		for (int j = 1; j <= 10; j++) {
			cin >> mp[i][j];
		}
	}

// 从外面开始进行 DFS 遍历
	dfs(0, 0);

int ans = 0;
	// 统计未被访问过的 0 的个数
	for (int i = 1; i <= 10; i++) {
		for (int j = 1; j <= 10; j++) {
			if (mp[i][j] == 0) ans++;
		}
	}
	cout << ans;

return 0;
}

```

0.0分

3 人评分

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

计科余定成

TA的其他文章

你可能喜欢

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

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

【计算球体积】（C语言代码）

逆反的01串（C++代码）（依旧推荐switch）

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

围成面积（搜索）

评论区

精彩推荐

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

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

C语言考试练习题_一元二次方程（C语言代码）

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

printf基础练习2 （C语言代码）

printf基础练习2 （有点不明白）

C二级辅导-阶乘数列（C语言代码）

【金明的预算方案】（C++代码）

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

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

计科余定成

TA的其他文章

你可能喜欢

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

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

【计算球体积】 （C语言代码）

逆反的01串 （C++代码）（依旧推荐switch）

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

围成面积（搜索）

评论区

精彩推荐

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

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

C语言考试练习题_一元二次方程 （C语言代码）

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

printf基础练习2 （C语言代码）

printf基础练习2 （有点不明白）

C二级辅导-阶乘数列 （C语言代码）

【金明的预算方案】 （C++代码）

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

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

【计算球体积】（C语言代码）

逆反的01串（C++代码）（依旧推荐switch）

　　评论区

C语言考试练习题_一元二次方程（C语言代码）

C二级辅导-阶乘数列（C语言代码）

【金明的预算方案】（C++代码）