2018年蓝桥杯JAVA B组“全球变暖”题目详解

对2018年蓝桥杯JAVA B组“全球变暖”题目详解

题目

标题：全球变暖
你有一张某海域NxN像素的照片，".“表示海洋、”#"表示陆地，如下所示：

其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
例如上图中的海域未来会变成如下样子：

请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
【输入格式】
第一行包含一个整数N。 (1 <= N <= 1000)
以下N行N列代表一张海域照片。
照片保证第1行、第1列、第N行、第N列的像素都是海洋。
【输出格式】
一个整数表示答案。
【输入样例】

【输出样例】
1
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是：Main，否则按无效代码处理。

思路：
1.由于二维字符矩阵不能直接存入char[][]矩阵中，所以使用String[i]间接存储，i为行数，String[i]记录第i+1行的字符序列，之后再通过String的toCharArray()方法将每行字符序列转换为char数组，这样就利用char[][]存储了二维字符序列。
注明：采用char[][]进行存储要优于String[]存储，因为后续需进行遍历操作，而使用String中的charAt()方法虽然也可达到相同效果，但效率相比于char[][]来说效率要差很多。
2.二维矩阵存储后，首先要统计未发生淹没过程时的岛屿数。首先两个for循环遍历矩阵每个字符，如果这个字符是陆地(’#’)且未曾访问过，则岛屿数+1，之后从该字符处进行深度搜索，目的将与该字符相连的所有陆地标记为已访问（同属于同一个岛屿）。
3.对于dfs方法中，首先需判断i,j是否超出矩阵边界，避免下标越界情况出现。之后将该字符处的访问标志为置1表示已访问过，然后依次判断该字符上右下左四个方向是否存在陆地且未曾访问过，如果存在则把找到的符合条件的字符作为当前字符，继续深搜，这样属于同一个岛屿的陆地访问标志都变成了1，且岛屿数只加过1次。
4.进行淹没过程。同样使用两个for循环逐个字符判断，如果陆地的上下左右四个方向中某个方向存在海洋，则该陆地将变为海洋。这里需注意，要避免前面的陆地变成海洋带来的影响，为了便于说明，举个例子，如下图所示。

淹没前
......
..###.
..###.
.####.
......正确淹没后
......      
......
...#..
......
......错误淹没后
......      
......
......
......
......

如果不考虑相互之间的影响，仅考虑上下左右四个方向是否存在海洋，存在就直接将陆地改为海洋，则会导致上图中的错误淹没后结果，因为前一个陆地淹没后，对于下一个要判断的相邻陆地来说，由于前一个陆地已经变为海洋，对于要判断的陆地的某个方向肯定存在海洋了，则该判断陆地将直接变为海洋，这很明显是错误的。为了避免前一个陆地修改后影响下一个陆地的判断，引入修改位vis[][]。
5.淹没过程结束后，再次使用dfs方法计算淹没后剩余的岛屿数，淹没前岛屿数与淹没后岛屿数相减，即消失的岛屿数。

详细代码如下：

import java.util.Scanner;public class Main {static int N;static int[][] dfs_vis;//dfs深度搜索  检查当前点上右下左四个方向是否同时满足陆地、未访问两个条件//满足条件就以该点为下一个检查点进行判读，同时将访问标志设为1static void dfs(char[][] a,int i,int j){if(i>=1&&i<N-1&&j<N-1&&j>=1){//访问标志设为1dfs_vis[i][j]=1;//上if(a[i-1][j]=='#'&&dfs_vis[i-1][j]==0){dfs(a,i-1,j);}//右if(i>=1&&j<N-1&&a[i][j+1]=='#'&&dfs_vis[i][j+1]==0){dfs(a,i,j+1);}//下if(i>=1&&j<N-1&&a[i+1][j]=='#'&&dfs_vis[i+1][j]==0){dfs(a,i+1,j);}//左if(i>=1&&j<N-1&&a[i][j-1]=='#'&&dfs_vis[i][j-1]==0){dfs(a,i,j-1);}}}public static void main(String[] args){Scanner scan=new Scanner(System.in);N=scan.nextInt();String[] s=new String[N];char[][] c=new char[N][N];dfs_vis=new int[N][N];for(int i=0;i<N;i++){s[i]=scan.next();}scan.close();int[][] vis=new int[N][N];for(int i=0;i<N;i++){c[i]=s[i].toCharArray();		}//未淹没岛屿数int pre_sum=0;for(int i=1;i<N-1;i++){for(int j=1;j<N-1;j++){if(c[i][j]=='#'&&dfs_vis[i][j]==0){dfs(c,i,j);pre_sum++;}}}//System.out.println(pre_sum);//淹没过程for(int i=1;i<N-1;i++){for(int j=1;j<N-1;j++){if(c[i][j]=='#'){if((c[i-1][j]=='.'&&vis[i-1][j]==0)||(c[i+1][j]=='.'&&vis[i+1][j]==0)||(c[i][j-1]=='.'&&vis[i][j-1]==0)||(c[i][j+1]=='.'&&vis[i][j+1]==0)){c[i][j]='.';vis[i][j]=1;}}}}//打印淹没后结果/*for(int i=0;i<N;i++){for(int j=0;j<N;j++){System.out.print(c[i][j]);}System.out.println();}*///淹没后岛屿数dfs_vis=new int[N][N];int now_sum=0;for(int i=1;i<N-1;i++){for(int j=1;j<N-1;j++){if(c[i][j]=='#'&&dfs_vis[i][j]==0){dfs(c,i,j);now_sum++;}}}//System.out.println(now_sum);//两者之差就是淹没的岛屿数System.out.println(pre_sum-now_sum);}
}

附一组测试用例

8
........
..####..
.####.#.
..##....
....#.#.
.#.###..
...###..
........

用了多组测试用例测试，结果都对了，但不知道是否还存在疏漏的地方，如果大家发现不对的地方，欢迎评论指正，我会第一时间改掉，免得误导别人……