题目描述

你有一张某海域 N×N 像素的照片，”.”表示海洋、”#”表示陆地，如下所示：

.......
.##....
.##....
....##.
..####.
...###.
.......

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

.......
.......
.......
.......
....#..
.......
.......

请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。

考点

连通块问题 flood fill BFS

思路

一开始怎么也不想不明白，还不理解。不理解什么呢，不理解的是什么样的陆地情况算是一个岛屿，给定的样例的岛屿是怎么划分的？题目对于岛屿描述的是 上下左右四个方向上连在一起的一片陆地组成一座岛屿

对于这个问题的理解本质上就是连通块 flood fill问题，也就是对于二维字符数组中的一个陆地为起点开始延伸，一层层的进行搜索，bfs,只能按照上下左右四个方向开始走，并且只能走一次，且必须是陆地，当无路可走的时候停下来。这就算一个连通块

在这个连通块的确定过程中顺便判断一共有多少个陆地，这个岛屿中多少个陆地会被淹没

陆地淹没的判断方法，就是对于当前的陆地的上下左右四个临界方向，如果存在海洋，则令变量sea=true,表示会被淹没
但是不可以终止循环，因为还需要判断是否存在一个陆地和当前的陆地的相连

比较两者的大小，判断这个岛屿（连通块）会不会被完全淹没

while循环语句中对陆地海洋越界的条件的判断，可以以灵活的方式展现，可以是不满足条件的时候就continue,进行下一次循环

也可以是直接判断是否满足条件

package dbfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

class Pair{
    int x;
    int y;

    public Pair(int x, int y) {
        super();
        this.x = x;
        this.y = y;
    }

}

public class 全球变暖 {

    /**
     * @param args
     * @throws IOException 
     * @throws NumberFormatException 
     */
    static int n;
    static int N=1010;
    static char g[][]=new char [N][N];
    static boolean st[][]=new boolean[N][N];
    static int dx[]={0,0,1,-1};
    static int dy[]={1,-1,0,0};

    public static boolean bfs(int stx,int sty) {
        Queue<Pair> queue = new LinkedList<Pair>();
        queue.offer(new Pair(stx, sty));
        //队列中的每一个元素一定是一个陆地
        st[stx][sty]=true;
        int total=0;
        //表示在这一个连通块上的陆地的数量，也就是岛屿中陆地的数量
        int bound=0;
        //表示有多少个陆地的上下左右四个方向上有海洋

        while(!queue.isEmpty()){
            Pair pair1 = queue.poll();
            total++;
            boolean sea=false;
            for(int i=0;i<4;i++){
                int x=pair1.x+dx[i];
                int y=pair1.y+dy[i];

                if(x >n || x<0 || y>n || y<0) continue;
                if(st[x][y]) continue;
                if(g[x][y]=='.'){
                    sea=true;
                    continue;
                }
                st[x][y]=true;
                queue.offer(new Pair(x, y));

            }
            if(sea) bound++;
        }

        //System.out.println(total+" "+bound);
        if(total==bound) return true;
        //表示岛屿中的所有的陆地都是和海洋相连，会被淹没
        return false;

    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
      BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
       n=Integer.parseInt(bufferedReader.readLine());

      for(int i=0;i<n;i++){
          String pString=bufferedReader.readLine();
          for(int j=0;j<n;j++){
              g[i][j]=pString.charAt(j);
          }
      }
      int cnt=0;
      //表示有多少个连通块会被完全淹没
      for(int i=0;i<n;i++){
          for(int j=0;j<n;j++){
              if(g[i][j]=='#' && !st[i][j]){
                  if(bfs(i, j)) cnt++;
              }
          }
      }
      System.out.println(cnt);

    }

}