当前位置：首页 > article >正文

【算法】【数组与矩阵模块】矩阵中的最短通路值

article 2025/1/11 14:57:26

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
给定一个0，1矩阵，从矩阵的左上角出发，求到矩阵右下角的最短通路值，如果没有通路，则返回0
如：
arr = $\begin{bmatrix} 1 & 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1\end{bmatrix}$
结果为12

解决方案

原问题：
使用广度优先遍历算法配合map计算
1、申请一个map矩阵，map[i][j]代表从 arr[0][0] 到 arr[i][j]的最短距离
2、通过广度优先遍历算法计算队列（广度优先算法需要一个队列）中的每一个坐标
3、对于每一个坐标，首先计算出坐标的上下左右中满足下列条件：
· 坐标已经被计算过（一定会有一个被计算了，否则没办法到当前位置）
· 坐标在上下左右四个坐标中，值是最小的（从起点过来的最短距离）
4、当前坐标的最小值就是，上下左右计算出来的最小值+1，判断是否是终点，如果是终点直接返回，否则，从该点继续出发将能够到达的上下左右并且没有被计算过的点都加入队列.

代码编写

java语言版本

原问题：
方法一:


    /**
     * 二轮测试：广度优先：求最短通路值
     * @param arr
     * @return
     */
    public static int getMinPathCp1(int[][] arr) {
        if (arr == null || arr.length == 0 || arr[0].length == 0
                || arr[0][0] == 0) {
            return 0;
        }
        int row = arr.length;
        int col = arr[0].length;
        // map[i][j] 代表到arr[i][j]的最短距离
        int[][] map = new int[row][col];
        map[0][0] = 1;
        // 队列用于广度优先遍历
        Queue<Coordinate> queue = new LinkedList<>();
        // 起点先进入
        queue.offer(new Coordinate(0, 0));
        while (!queue.isEmpty()) {
            Coordinate poll = queue.poll();
            // 选出四周的：不为零、最小值
            int min = getMinPathCp2(map, poll);
            // 先判断是否到终点了
            if (poll.getRow() == row-1 && poll.getCol() == col-1) {
                return min+1;
            }
            map[poll.getRow()][poll.getCol()] = min+1;
            addNextSkip(queue, map, arr, poll);
        }
        // 出来说明循环结束但是没有到终点
        return 0;
    }

    /**
     * 将下一跳的节点放入
     * @param queue
     * @param map
     * @param arr
     * @param poll
     */
    private static void addNextSkip(Queue<Coordinate> queue, int[][] map, int[][] arr, Coordinate poll) {
        int row = poll.getRow();
        int col = poll.getCol();
        // 每一个节点需要满足要求：1、节点在map中没有计算过2、节点位置为1
        if (col - 1 >= 0 && map[row][col-1] == 0 && arr[row][col-1] == 1) {
            queue.add(new Coordinate(row, col-1));
        }
        if (col + 1 < map[0].length && map[row][col+1] == 0 && arr[row][col+1] == 1) {
            queue.add(new Coordinate(row, col+1));
        }
        if (row-1 >= 0 && map[row-1][col] == 0 && arr[row-1][col] == 1) {
            queue.add(new Coordinate(row-1, col));
        }
        if (row+1 < map.length && map[row+1][col] == 0 && arr[row+1][col] == 1) {
            queue.add(new Coordinate(row+1, col));
        }
    }

    /**
     * 选出四周计算过的最小值
     * @param map
     * @param poll
     * @return
     */
    private static int getMinPathCp2(int[][] map, Coordinate poll) {
        int row = poll.getRow();
        int col = poll.getCol();
        int left = Integer.MAX_VALUE;
        int right = Integer.MAX_VALUE;
        int top = Integer.MAX_VALUE;
        int down = Integer.MAX_VALUE;
        if (col - 1 >= 0 && map[row][col-1] != 0) {
             // 计算过
            left = map[row][col-1];
        }
        if (col + 1 < map[0].length && map[row][col+1] != 0) {
            right = map[row][col+1];
        }
        if (row-1 >= 0 && map[row-1][col] != 0) {
            top = map[row-1][col];
        }
        if (row+1 < map.length && map[row+1][col] != 0)
        {
            down = map[row+1][col];
        }
        int res =  Math.min(top, Math.min(left, Math.min(right, down)));
        return res == Integer.MAX_VALUE ? 0 : res;
    }


    /**
     * 坐标
     */
    static class Coordinate {
        private int row;
        private int col;


        public Coordinate(int row, int col) {
            this.row = row;
            this.col = col;
        }

        public int getRow() {
            return row;
        }

        public void setRow(int row) {
            this.row = row;
        }

        public int getCol() {
            return col;
        }

        public void setCol(int col) {
            this.col = col;
        }

        @Override
        public String toString() {
            return "Coordinate{" +
                    "row=" + row +
                    ", col=" + col +
                    '}';
        }
    }



    public static void main(String[] args) {
        System.out.println(getMinPathCp1(new int[][]{
                {1,0,1,1,1},
                {1,0,1,0,1},
                {1,1,1,0,1},
                {0,0,0,0,1}
        }));
    }

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

首先这道题需要注意的几个点：
1、边界值需要注意检查上下左右的时候周边不能越界
2、广度优先遍历每一次进入队列的点必须是没有计算过的才行，如果被计算过，还被加入队列了会导致无限的死循环，因为矩阵中的广度优先跟树不一样，树形结构不存在环路
3、我起初有点怀疑最后计算出来的答案会不会不是最短的距离，比如在计算出结果之前已经有点到达了这里，并且将不是最优解的解赋值给了结果并返回了，会不会出现这种情况？？？
其实不会出现这种情况，因为长的路线进入队列的元素会多，短的路线进入队列的元素会少，当两条线路同时进入队列的时候，短的线路已经会最先遍历完成并到达终点。
4、还有一种情况就是两条速度一样的线路交叉了怎么办
比如：
$\begin{bmatrix} 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1\end{bmatrix}$
这里我通过debug方式发现确实存在一个优化点，也就是说从arr[0][0]出发后，arr[1][0]和arr[0][1]会进入队列，那么接下来的逻辑会将arr[1][1]加入两次，从这里开始后面的所有点都会被加入两次，因此需要添加一个判断，加入时如果队尾的坐标和加入的坐标已经重合了，那么不再加入这个位置了。