【蓝桥杯真题】全球变暖

全球变暖（2018年第九届蓝桥杯JavaA组省赛 第八题）

【题目描述】

你有一张某海域NxN像素的照片，".“表示海洋、”#"表示陆地，如下所示： … .##… .##… …##. …####. …###. … 其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。 由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。 具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。 例如上图中的海域未来会变成如下样子： … … … … …#… … … 请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。

【输入格式】

第一行包含一个整数N。 (1 <= N <= 1000) 以下N行N列代表一张海域照片。 照片保证第1行、第1列、第N行、第N列的像素都是海洋。

【输出格式】

一个整数表示答案。

【样例输入】

7 … .##… .##… …##. …####. …###. …

【样例输出】

1

测试网址：

个人解法

【解法一】

代码：

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class _全球变暖 {
          
   
	
	static char[][] rv;
	static int n;
	
	public static void main(String[] args) {
          
   
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		rv = new char[n][n];
		for(int i=0; i<n; ++i)
			rv[i] = sc.next().toCharArray();
		
		int ans = 0;
		for(int i=1; i<n-1; ++i) {
          
   
			for(int j=1; j<n-1; ++j) {
          
   
				if(rv[i][j] == #) {
          
   
					ans += bfs(i, j);	
				}
			}
		}
		System.out.println(ans);
	}
	
	
	static Queue<Integer> que = new LinkedList<Integer>();
	static int[][] dir = new int[][] {
          
   {
          
   -1, 0}, {
          
   0, -1}, {
          
   1, 0}, {
          
   0, 1}};
	
	/**
	 * 	广搜当前的小岛，如果存在一个陆地像素的四个方向全都是陆地像素时，说明这座岛没有被淹没；ans表示被淹没的数量，0表示当前的小岛没被淹没
	 * @param x
	 * @param y
	 * @return
	 */
	public static int bfs(int x, int y) {
          
   
		int ans = 1;
		rv[x][y] = *;
		que.add(x*n+y);
		while(!que.isEmpty()) {
          
   
			int p = que.poll();
			int cx = p/n, cy = p%n;
			boolean record = true;
			for(int i=0; i<dir.length; ++i) {
          
   
				int nx = cx+dir[i][0], ny = cy+dir[i][1];
				if(rv[nx][ny]==#) {
          
   
					rv[nx][ny] = *;
					que.add(nx*n+ny);
				}else if(rv[nx][ny] == .){
          
   
					record = false;
				}
			}
			if(record)
				ans = 0;
		}
		return ans;
	}

}