题解 | 2023_高尔夫比赛的森林砍树_1369按顺序访问多次bfs计算最短路

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt(), n = sc.nextInt();
        int[][] matrix = new int[m][n];
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = sc.nextInt();
                if (matrix[i][j] > 1) list.add(new int[] {matrix[i][j], i, j});
            }
        }
        list.sort(Comparator.comparingInt(o -> o[0]));
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {0, 0});
        int ans = 0;
        int x = 0, y = 0;
        for (int[] tree : list) {
            int nx = tree[1], ny = tree[2];
            if (nx == 0 && ny == 0) continue;
            int step = bfs(matrix, x, y, nx, ny);
            if (step == -1) {
                System.out.println(-1);
                return;
            }
            ans += step;
            x = nx;
            y = ny;
        }
        System.out.println(ans);
        sc.close();
    }

    private static int bfs(int[][] matrix, int x, int y, int a, int b) {
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[matrix.length][matrix[0].length];
        final int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        queue.offer(new int[] {x, y});
        visited[x][y] = true;
        int step = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            step++;
            while (size-- > 0) {
                int[] cur = queue.poll();
                for (int[] direction : directions) {
                    int nx = cur[0] + direction[0], ny = cur[1] + direction[1];
                    if (nx == a && ny == b) return step;
                    if (nx < 0 || nx >= matrix.length || ny < 0 || ny >= matrix[0].length ||
                            visited[nx][ny] || matrix[nx][ny] == 0)
                        continue;
                    visited[nx][ny] = true;
                    queue.offer(new int[] {nx, ny});
                }
            }
        }
        return -1;
    }
}