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

2251 阅读 5 评论 0 点赞

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

12 人评分

本文分类：题解列表
浏览次数：2251 次浏览
发布日期：2023-04-09 11:35:17
本文链接：https://blog.dotcpp.com/a/95772

上一篇 > 2860基础解法（Python）
下一篇 > 蓝桥杯2023年第十四届省赛真题-子串简写（DP）

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

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

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

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

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

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

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

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

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

评论列表共有 5 条评论

发表评论取消回复

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

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

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 5 条评论

发表评论 取消回复

评论列表共有 5 条评论

发表评论取消回复