2道题的思路相近

第一道题：岛屿数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：
输入：grid = [
[“1”,“1”,“1”,“1”,“0”],
[“1”,“1”,“0”,“1”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“0”,“0”,“0”]
]
输出：1
示例 2：

输入：grid = [
[“1”,“1”,“0”,“0”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“1”,“0”,“0”],
[“0”,“0”,“0”,“1”,“1”]
]
输出：3

原题链接：https://leetcode.cn/problems/number-of-islands

    public int numIslands(char[][] grid) {
        int result = 0;

        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j] == '1'){
                    result++;
                    helper(grid,i,j);
                }
            }
        }

        return result;
    }

    // 感染函数，深度优先遍历
    private void helper(char[][]grid,int i,int j){
        if(i<0 || i>=grid.length || j<0 || j>=grid[0].length || grid[i][j] != '1'){
            return;
        }
        // 已经计算过
        grid[i][j] = '2';
        helper(grid,i+1,j);
        helper(grid,i-1,j);
        helper(grid,i,j+1);
        helper(grid,i,j-1);
    }

第二道题：按图找最近的路径

有一张m*n的地图，地图描述了起点和终点的位置，也描述了两点间分布的高山湖泊，高山湖泊挡住去路，需要绕道行走，请问从起点到终点的最短路径有几条，距离是多少？

注意：走动路线只能上下左右，不能斜着走。

输入描述
假设是5*5的地图，那么四个角的坐标表示为(0,0)，(0,4) ，(4,4) ，(4,0)；

起点是(0,1)，重点是(3,3)

高山湖泊的个数：1

高山湖泊的位置 (2,2)

输入表示：
5 5 ——图的大小
0 1 ——起点坐标
3 3 ——终点坐标
1 ——湖泊个数
2 2 ——湖泊坐标

注意：坐标的单位长度为1

输出描述
最短路径有4条，距离是5，输出格式是 4 5

输入

5 5
0 1
3 3
1
2 2

输出

4 5

    static int minLen = Integer.MAX_VALUE;
    static int path = 0;

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int rowSize = sc.nextInt();
        int colSize = sc.nextInt();

        int[][] map = new int[rowSize][colSize];

        // 将所有点标记为0,可以省略
        for (int i = 0; i < rowSize; i++) {
            for (int j = 0; j < colSize; j++) {
                map[i][j] = 0;
            }
        }

        int startX = sc.nextInt();
        int startY = sc.nextInt();

        int endX = sc.nextInt();
        int endY = sc.nextInt();

        int LakeNum = sc.nextInt();

        // 高山湖泊设为1
        for (int i = 0; i < LakeNum; i++) {
            int lakeX = sc.nextInt();
            int lakeY = sc.nextInt();
            map[lakeX][lakeY] = 1;
        }

        helper(map, startX, startY, endX, endY,0);
        System.out.println(path + " " + minLen);
    }

    private static void helper(int[][] map, int startX, int startY, int endX, int endY, int len) {
        int rowSize = map.length;
        int colSize = map[0].length;

        // 越界、碰壁情况直接返回
        if (startX >= rowSize || startX < 0 || startY >= colSize || startY < 0 || map[startX][startY] != 0) {
            return;
        }

        if (startX == endX && startY == endY) {
            if (len < minLen){
                path = 1;
                minLen = len;
            } else if (len == minLen) {
                path++;
            }
            return;
        }else{
            // 继续寻找，mark一下这里已经走过了
            map[startX][startY] = 1;
            // 上下左右各种移动
            helper(map, startX+1, startY, endX, endY,len+1);
            helper(map, startX-1, startY, endX, endY,len+1);
            helper(map, startX, startY+1, endX, endY,len+1);
            helper(map, startX, startY-1, endX, endY,len+1);
            // 回溯完记得mark回去
            map[startX][startY] = 0;
        }
    }