蓝桥杯 全球变暖

本文主要是介绍蓝桥杯 全球变暖，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem: 蓝桥杯 全球变暖

思路

这道题目可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来解决。我们需要遍历整个地图，当遇到陆地（‘#’）时，就进行搜索，统计这个岛屿的总陆地数量和边界陆地数量。如果这两个数量相等，说明这个岛屿会被完全淹没。

解题方法

初始化一个队列，用于存储需要搜索的陆地位置。
遍历整个地图，当遇到未被访问过的陆地时，将其加入队列，并标记为已访问。
进行 BFS 搜索，每次从队列中取出一个陆地位置，然后检查其四个方向的像素。如果是陆地且未被访问过，就加入队列；如果是海洋，就将当前陆地标记为边界陆地。
当队列为空时，搜索结束，返回总陆地数量和边界陆地数量。
如果总陆地数量等于边界陆地数量，就将岛屿数量加一。

复杂度

时间复杂度:

$O(n^2)$，需要遍历整个地图，n 是地图的边长。

空间复杂度:

$O(n^2)$，需要存储地图和访问状态，n 是地图的边长。

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;public class Main {static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer sr = new StreamTokenizer(in);static int MAXN = (int) (1e3 + 10);static char[][] grip = new char[MAXN][MAXN];static boolean[][] st = new boolean[MAXN][MAXN];static int n;static Queue<int[]> queue = new LinkedList<>();static int[][] move = { {}, { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };public static void main(String[] args) throws IOException {n = nextInt();
//		in.readLine(); // 吃掉换行符for (int i = 0; i < n; i++) {grip[i] = in.readLine().toCharArray();}int cnt = 0;for (int a = 0; a < n; a++) {Arrays.fill(st[0], false);}for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (!st[i][j] && grip[i][j] == '#') {int[] result = bfs(i, j);int total = result[0];int bound = result[1];if (total == bound)cnt++;}}}out.println(cnt);out.flush();}private static int[] bfs(int x, int y) {// TODO Auto-generated method stubint total = 0, bound = 0;queue.offer(new int[] { x, y });st[x][y] = true;while (!queue.isEmpty()) {int[] arr = queue.poll();int nx = arr[0];int ny = arr[1];total++;boolean is_bound = false;for (int i = 1; i <= 4; i++) {int dx = nx + move[i][0];int dy = ny + move[i][1];// 越界if (dx < 0 || dy < 0 || dx >= n || dy >= n || st[dx][dy])continue;// 如果遇到.if (grip[dx][dy] == '.') {is_bound = true;continue;}queue.offer(new int[] { dx, dy });st[dx][dy] = true;}if (is_bound) {bound++;}}return new int[] {total, bound};}private static int nextInt() throws IOException {sr.nextToken();return (int) sr.nval;}}

这篇关于蓝桥杯 全球变暖的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---