计科余定成

用户名：dotcpp0598358

访问量：13826

签　名：

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

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

　　自我简介：

我是余定成

TA的其他文章

[STL训练]周瑜的反间计
浏览：84

后缀表达式的值
浏览：246

3077: 信息学奥赛一本通T1332-周末舞会
浏览：272

你可能喜欢

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

　　作者: 计科余定成　　　　发表时间：2023-04-09 11:35:17 浏览：2130　|　评论：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语言代码）

字符串的输入输出处理（C语言代码）

点我有惊喜！你懂得！

母牛的故事（C语言代码）

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

评论区

精彩推荐

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

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

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

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

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

Tom数（C语言代码）

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

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

C二级辅导-分段函数（C语言代码）

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

计科余定成

TA的其他文章

你可能喜欢

宏定义

十->二进制转换 （C语言代码）

字符串的输入输出处理 （C语言代码）

点我有惊喜！你懂得！

母牛的故事 （C语言代码）

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

评论区

精彩推荐

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

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

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

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

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

Tom数 （C语言代码）

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

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

C二级辅导-分段函数 （C语言代码）

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

十->二进制转换（C语言代码）

字符串的输入输出处理（C语言代码）

母牛的故事（C语言代码）

　　评论区

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

Tom数（C语言代码）

C二级辅导-分段函数（C语言代码）