大学生兼职网网站建设计划书,制作一个动态企业网站,哈尔滨信息网,昆山网站建设怎么样Problem: 蓝桥杯 全球变暖 文章目录 思路解题方法复杂度Code 思路 这道题目可以使用深度优先搜索#xff08;DFS#xff09;或广度优先搜索#xff08;BFS#xff09;来解决。我们需要遍历整个地图#xff0c;当遇到陆地#xff08;‘#’#xff09;时#xff0c;就进行… Problem: 蓝桥杯 全球变暖 文章目录 思路解题方法复杂度Code 思路 这道题目可以使用深度优先搜索DFS或广度优先搜索BFS来解决。我们需要遍历整个地图当遇到陆地‘#’时就进行搜索统计这个岛屿的总陆地数量和边界陆地数量。如果这两个数量相等说明这个岛屿会被完全淹没。 解题方法 初始化一个队列用于存储需要搜索的陆地位置。 遍历整个地图当遇到未被访问过的陆地时将其加入队列并标记为已访问。 进行 BFS 搜索每次从队列中取出一个陆地位置然后检查其四个方向的像素。如果是陆地且未被访问过就加入队列如果是海洋就将当前陆地标记为边界陆地。 当队列为空时搜索结束返回总陆地数量和边界陆地数量。 如果总陆地数量等于边界陆地数量就将岛屿数量加一。 复杂度
时间复杂度: O ( n 2 ) O(n^2) O(n2)需要遍历整个地图n 是地图的边长。 空间复杂度: O ( n 2 ) O(n^2) O(n2)需要存储地图和访问状态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 Queueint[] 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;}}
