2022.03.30华为前端、后端算法第二题_给定一个m*n的整数矩阵作为地图,矩阵数值为地形高度,中庸行者选择其中任意一

严正声明：转载请注明出处！！！

题目描述

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

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

输入

假设是5*5的地图，那么四个角的坐标表示为(0, 0), (0, 4), (4, 4), (4, 0)；
起点是(0, 1)，终点是(3, 3)
高山湖泊的个数：1
高山湖泊的位置(2, 2)
输入表示：
5 5——图的大小是5 5
0 1——起点坐标
3 3——终点坐标
1——湖泊个数
2 3——湖泊坐标
注意：坐标的单位长度为1
1
2
3
4
5
6
7
8
9
10
11

输出

最短路径有4条，距离是5；输出格式：4 5
1

样例1

输入

5 5
1 0
3 3
2
2 2
2 1
1
2
3
4
5
6

输出

2 5
1

import java.util.Scanner;
public class Main {
    public static int min = Integer.MAX_VALUE;
    public static int count = 0;

    public static void dfs(int[][] nums, boolean[][] visited, int i, int j, int endX, int endY, int sum) {
        if (i < 0 || i >= nums.length || j < 0 || j >= nums[0].length || visited[i][j] || nums[i][j] == 1) {
            return;
        }
        if (i == endX && j == endY) {
            if (sum < min) {
                min = sum;
                count = 1;
            } else if (sum == min) {
                count++;
            }
            return;
        }
        visited[i][j] = true;
        dfs(nums, visited, i + 1, j, endX, endY, sum + 1);
        dfs(nums, visited, i - 1, j, endX, endY, sum + 1);
        dfs(nums, visited, i, j + 1, endX, endY, sum + 1);
        dfs(nums, visited, i, j - 1, endX, endY, sum + 1);
        visited[i][j] = false;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        int n = scanner.nextInt();
        int startX = scanner.nextInt();
        int startY = scanner.nextInt();
        int endX = scanner.nextInt();
        int endY = scanner.nextInt();
        int num = scanner.nextInt();
        int[][] lake = new int[num][2];
        int[][] nums = new int[m][n];
        for (int i = 0; i < num; i++) {
            lake[i][0] = scanner.nextInt();
            lake[i][1] = scanner.nextInt();
            nums[lake[i][0]][lake[i][1]] = 1;
        }
        boolean[][] visited = new boolean[m][n];
        dfs(nums, visited, startX, startY, endX, endY, 0);
        System.out.println(count + " " + min);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48