整体思路

  1. 在输入的图中，首先选取一个可以走的点。（是陆地，且没有被访问过）
  2. 然后根据这一个点，使用BFS或者DFS向四周去扩张，把所有能扩张的全访问一遍
  3. 最终，最上层找到几个能访问的点，就是几个独立岛屿
  4. 这个题目说白了就是图的寻找连通块一样

    题目细节

  • 使用方向数组表示行进方向
  • 上 左，下，右
  • dx = {-1, 0, 0, 1}
  • dy = {0, -1, 1, 0}
  1. class Solution {
  2.     //记录一下子输入数据，省着下传了
  3.     private char[][] grid;
  4.     //记录一下子行数和列数，作为共享变量
  5.     int rowNum;
  6.     int colNum;
  7.     //创建一个和输入一样大小的二维数组，以此记录一个点是否被访问过
  8.     boolean[][] vistied;
  9.     public int numIslands(char[][] grid) {
  10.         this.grid = grid;
  11.         this.rowNum = grid.length;
  12.         this.colNum = grid[0].length;
  13.         vistied = new boolean[rowNum][colNum];
  14.         //答案
  15.         int ans = 0;
  17.         //遍历整个输入的二维数组，选取一个没有被访问过的且为1的点，然后使用bfs去四周扩张，只到把可访问的点全部扩张完成且访问
  18.         for(int i = 0;i < rowNum;i++){
  19.             for(int j = 0;j < colNum;j++){
  20.                 if(grid[i][j] == '1' && !vistied[i][j]){
  21.                     //答案+1 找到一个没有被访问的过岛屿，答案就加一。这是因为下面bfs会把找到的每一个岛屿全访问完的
  22.                     //所以只要找到的岛屿，就是新的岛屿
  23.                     ans++;
  24.                     bfs(i,j);
  25.                 }
  26.             }
  27.         }
  28.         return ans;
  29.     }
  31.     public void bfs(int x,int y){
  32.         //只要是广度优先遍历，就先把队列拿出来
  33.         Queue<Pair<Integer,Integer>> queue = new LinkedList<>();
  34.         //方向数组（记录行进方向的值），也就是x y + 方向数组的值 = 下一个点的坐标
  35.         //                   上, 左, 右,下
  36.         int[] dx = new int[]{-1, 0, 0, 1};
  37.         int[] dy = new int[]{0, -1, 1, 0};
  39.         //把当前点放入队列中去
  40.         queue.add(new Pair<>(x,y));
  41.         while (!queue.isEmpty()){
  42.             //1:队头出队，记录当前点
  43.             Pair<Integer, Integer> point = queue.poll();
  44.             int nowX = point.getKey();
  45.             int nowY = point.getValue();
  46.             //记录这个点已经被访问过了
  47.             vistied[nowX][nowY] = true;
  49.             //2:以当前点为圆心，想上下左右扩张，能走的地方就标记访问
  50.             for(int i = 0;i < 4; i++){
  51.                 //获取到当前点的下一个方向的点的坐标
  52.                 int nextX = nowX + dx[i];
  53.                 int nextY = nowY + dy[i];
  55.                 //如果新的点超过边界了，就忽略这个点
  56.                 if(nextX < 0 || nextX >= rowNum || nextY < 0 || nextY >= colNum){
  57.                     continue;
  58.                 }
  59.                 //如果新的点不是岛屿则忽略这给点
  60.                 if(grid[nextX][nextY] != '1'){
  61.                     continue;
  62.                 }
  63.                 //如果新的点已经被访问过了则忽略这个点
  64.                 if(vistied[nextX][nextY]){
  65.                     continue;
  66.                 }
  67.                 //如果上面条件都不满足，说明是新点是一个没被访问的合法的陆地，那么就把这个点入队让他继续扩张去，然后记录已访问
  68.                 queue.add(new Pair<>(nextX,nextY));
  69.                 vistied[nextX][nextY] = true;
  70.             }
  71.         }
  72.     }
  73. }