计科余定成

用户名：dotcpp0598358

访问量：15777

签　名：

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

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

　　自我简介：

我是余定成

TA的其他文章

蓝桥杯2022年第十三届省赛真题-重新排序
浏览：1129

图的遍历-DFS
浏览：56

求具有abcd=(ab+cd)2性质的四位数
浏览：73

你可能喜欢

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

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

蓝桥杯2023年第十四届省赛真题-岛屿个数（搜索）

　　作者: 计科余定成　　　　发表时间：2023-04-09 11:35:17 浏览：2207　|　评论：4　

原题链接：蓝桥杯2023年第十四届省赛真题-岛屿个数

# ***解题思路***
从$$(0,0)$$开始染色，把遇到的0全部染成2，这样没染色的部分，一定为环，接着再搜索环的个数即可。

注意：开始染色的时候，可能有斜角，得使用八向搜索；搜索环的时候则用四向搜索。

------------

# ***参考代码***
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e1 + 5;
int T, m, n;
char g[N][N];
int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1};
int dy[8] = {1, -1, 0, 0, -1, 1, 1, -1};
int ans;
struct point {
	int x, y;
};
void bfs1() {
	queue<point>q;
	g[0][0] = '2';
	q.push({0, 0});
	while (!q.empty()) {
		point now = q.front();
		q.pop();
		for (int i = 0; i < 8; i++) {
			int tx = now.x + dx[i];
			int ty = now.y + dy[i];
			if (tx >= 0 && ty >= 0 && tx <= m + 1 && ty <= n + 1) {
				if (g[tx][ty] == '0') {
					g[tx][ty] = '2';
					q.push({tx, ty});
				}
			}
		}
	}
}
void bfs2(int x, int y) {
	queue<point>q;
	g[x][y] = '2';
	q.push({x, y});
	while (!q.empty()) {
		point now = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int tx = now.x + dx[i];
			int ty = now.y + dy[i];
			if (tx >= 1 && ty >= 1 && tx <= m && ty <= n) {
				if (g[tx][ty] == '0' || g[tx][ty] == '1') {
					g[tx][ty] = '2';
					q.push({tx, ty});
				}
			}
		}
	}
}
int main() {
	cin >> T;
	while (T--) {
		cin >> m >> n;
		memset(g, '0', sizeof(g));
		ans = 0;
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= n; j++) {
				cin >> g[i][j];
			}
		}
		bfs1();
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= n; j++) {
				if (g[i][j] == '1') {
					ans++;
					bfs2(i, j);
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}

```

0.0分

20 人评分

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

　　评论区

llllllll

思路跟我一样

2024-03-07 20:22:17

腾汛视频

写下自己的关键理解：//处理环的时候四向染色会直接往里面染然后子岛屿也被视为同一（0/1都染）
//而有漏洞的非环会被8向染色染进去2然后阻断了外侧向内的染色，这样统计的时候里面的就不会漏掉

2023-05-30 23:18:18

马路杀手刘沛松

很强

2023-05-05 10:51:21

本人学渣

很nice兄弟

2023-04-12 18:16:39

计科余定成

TA的其他文章

你可能喜欢

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

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

【密码】（C语言代码）

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

WU-蓝桥杯算法提高VIP-交换Easy （C++代码）

蓝桥杯2023年第十四届省赛真题-岛屿个数（搜索）

评论区

精彩推荐

幸运数（C++代码）

剪刀石头布（C++代码）

前10名（C语言代码）

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

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

【出圈】（C++代码）简单循环

1073题解

龟兔赛跑预测（C++代码）

C语言训练-求车速（C语言代码）

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

计科余定成

TA的其他文章

你可能喜欢

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

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

【密码】 （C语言代码）

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

WU-蓝桥杯算法提高VIP-交换Easy （C++代码）

蓝桥杯2023年第十四届省赛真题-岛屿个数（搜索）

评论区

精彩推荐

幸运数 （C++代码）

剪刀石头布 （C++代码）

前10名 （C语言代码）

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

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

【出圈】 （C++代码）简单循环

1073题解

龟兔赛跑预测 （C++代码）

C语言训练-求车速 （C语言代码）

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

【密码】（C语言代码）

　　评论区

幸运数（C++代码）

剪刀石头布（C++代码）

前10名（C语言代码）

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

【出圈】（C++代码）简单循环

龟兔赛跑预测（C++代码）

C语言训练-求车速（C语言代码）