利用BFS解决每个零售店到仓库最短距离之和问题

1、题目

矩阵中有3种类型：0仓库，-1障碍，1零售店。现在每个零售店要去距离它最近的仓库取货物，请计算出所有零售店到最近仓库距离之和，假设矩阵中每个单元格之间距离为1。如果遇到障碍物，则表示无法通过。可以在单元格上下左右移动。
注意
无法到达仓库的零售店不参与计算
没有零售店或者没有仓库，则返回0

2、用例

第一行输入3 3代表3×3矩阵
第二行输入矩阵值
第三行输出最短距离和
3 3
1 -1 0
0 1 1
1 -1 1
结果为6

3、算法

BFS

public class BFS {
    // 0仓库，-1障碍，1零售店
    // 无法到达仓库的零售店不参与计算
    // 没有零售店或者没有仓库，则返回0
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in, StandardCharsets.UTF_8.name());
        int rows = cin.nextInt();
        int cols = cin.nextInt();
        int[][] grids = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                grids[i][j] = cin.nextInt();
            }
        }
        cin.close();
        System.out.println(nearestWareHouse(grids));
    }

    private static int nearestWareHouse(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        // 仓库节点坐标
        Queue<int[]> visitQueue = new LinkedList<>();
        // 遍历grid，把所有仓库节点坐标放入bfs队列
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 0) {
                    // 如果是仓库节点，入队，设置visited[i][j] = true
                    visitQueue.add(new int[]{i, j});
                }
            }
        }
        // 初始化步长为1，此时队列中为仓库，以仓库为中心，以1为步长，向四周扩散
        // 将已遍历的节点设置为-1
        int step = 1;
        int result = 0;
        while (!visitQueue.isEmpty()) {
            int qcount = visitQueue.size();
            for (int i = 0; i < qcount; i++) {
                // 出队列，向该节点四周扩散
                // poll从队列中移除并返回头部元素
                int[] temp = visitQueue.poll();
                int x = temp[0];
                int y = temp[1];
                // 右边
                if (x + 1 < rows && grid[x + 1][y]==1) {
                    result += step;
                    grid[x + 1][y] = -1;
                    visitQueue.add(new int[]{x + 1, y});
                }
                // 左边
                if (x - 1 >= 0 && grid[x - 1][y]==1) {
                    result += step;
                    grid[x - 1][y] = -1;
                    visitQueue.add(new int[]{x - 1, y});
                }
                // 上面
                if (y - 1 >= 0 && grid[x][y - 1]==1) {
                    result += step;
                    grid[x][y - 1] = -1;
                    visitQueue.add(new int[]{x, y - 1});
                }
                // 下面
                if (y + 1 < cols && grid[x][y + 1]==1) {
                    result += step;
                    grid[x][y + 1] = -1;
                    visitQueue.add(new int[]{x, y + 1});
                }
            }
            step++;
        }
        return result;
    }
}

BFS2

static class Point {

        int x;
        int y;
        int step;

        public Point(int x, int y, int step) {
            this.x = x;
            this.y = y;
            this.step = step;
        }
    }

    private static int nearestWareHouse(int[][] grid) {
        int result = 0;
        int rows = grid.length;
        int cols = grid[0].length;
        Queue<Point> queue = new LinkedList<>();
        // 遍历grid，把所有仓库节点坐标放入bfs队列
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 0) {
                    // 如果是仓库节点，入队
                    queue.add(new Point(i, j, 0));
                }
            }
        }

        while (!queue.isEmpty()) {
            Point point = queue.poll();
            int x = point.x;
            int y = point.y;
            // 左
            if (x != 0 && grid[x - 1][y] == 1) {
                queue.add(new Point(x - 1, y, point.step + 1));
                grid[x - 1][y] = -1;
            }
            // 右
            if (x != rows - 1 && grid[x + 1][y] == 1) {
                queue.add(new Point(x + 1, y, point.step + 1));
                grid[x + 1][y] = -1;
            }
            // 上
            if (y != 0 && grid[x][y - 1] == 1) {
                queue.add(new Point(x + 1, y, point.step + 1));
                grid[x + 1][y] = -1;
            }
            // 下
            if (y != cols - 1 && grid[x][y + 1] == 1) {
                queue.add(new Point(x, y + 1, point.step + 1));
                grid[x][y + 1] = -1;
            }
            result += point.step;
        }
        return result;
    }

BFS3

private static int nearestWareHouse(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        // 仓库节点坐标
        Queue<int[]> visitQueue = new LinkedList<>();
        // 记录已访问和未访问标记
        boolean[][] visited = new boolean[rows][cols];
        // 遍历grid，把所有仓库节点坐标放入bfs队列
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 0) {
                    // 如果是仓库节点，入队，设置visited[i][j] = true，设置未访问过
                    visitQueue.add(new int[]{i, j});
                    visited[i][j] = false;
                } else if (grid[i][j] == -1) {
                    // 障碍物，设置未访问过
                    visited[i][j] = false;
                } else {
                    // 仓库，设置已访问过
                    visited[i][j] = true;
                }
            }
        }
        // 初始化步长为1，此时队列中为仓库，以仓库为中心，以1为步长，向四周扩散
        // 将已遍历的节点设置为-1
        int step = 1;
        int result = 0;
        while (!visitQueue.isEmpty()) {
            int qcount = visitQueue.size();
            for (int i = 0; i < qcount; i++) {
                // 出队列，向该节点四周扩散
                // poll从队列中移除并返回头部元素
                int[] temp = visitQueue.poll();
                int x = temp[0];
                int y = temp[1];
                // 右边
                if (x + 1 < rows && visited[x + 1][y]) {
                    result += step;
                    visited[x + 1][y] = false;
                    visitQueue.add(new int[]{x + 1, y});
                }
                // 左边
                if (x - 1 >= 0 && visited[x - 1][y]) {
                    result += step;
                    visited[x - 1][y] = false;
                    visitQueue.add(new int[]{x - 1, y});
                }
                // 上面
                if (y - 1 >= 0 && visited[x][y - 1]) {
                    result += step;
                    visited[x][y - 1] = false;
                    visitQueue.add(new int[]{x, y - 1});
                }
                // 下面
                if (y + 1 < cols && visited[x][y + 1]) {
                    result += step;
                    visited[x][y + 1] = false;
                    visitQueue.add(new int[]{x, y + 1});
                }
            }
            step++;
        }
        return result;
    }