【算法】迷宫问题

快来打我* 2022-05-23 08:30 232阅读 0赞

【题目】

用一个整型矩阵matrix表示一个迷宫，0代表路，1代表墙，求从左上角到右下角的最短通路。

例如：

![20180605172443514][]

【解答】

使用广度优先遍历即可。

1.开始时生成map矩阵， map\[i\]\[j\]的含义是从(0,0)位置走到(i,j)位置最短的路径值。然后将入口位置(0,0)的行坐标和列坐标放入行队列和列队列。

2.不断地从队列弹出一个位置(r,c)，然后看这个位置的上下左右四个位置哪些在matrix上的位置是0，这些都是路。

3.将那些路设置好各自在map中的值，即map\[r\]\[c\]+1。同时将这些位置加入到rQ和cQ中，用队列完成宽度优先遍历。

4.在3中，如果一个位置之前走过，就不要重复走。map\[i\]\[j\]!=0时，即已经走过了。

5.重复步骤2~4，直到走到终点，如果rQ和cQ为空都没有遇到终点位置，说明不存在这样的路径。

import java.util.*;
    public class Main {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            while (sc.hasNext()) {
                int m = sc.nextInt();
                int n = sc.nextInt();
                int[][] ma = new int[m][n];
                for (int i = 0; i < m; i++) {
                    for (int j = 0; j < n; j++) {
                        ma[i][j] = sc.nextInt();
                    }
                }
                Queue<Node> res = minPath(ma);
                for (Node node : res) {
                    System.out.println("(" + node.r + "," + node.c + ")");
                }
            }
            sc.close();
        }
        public static Queue<Node> minPath(int[][] ma) {
            if (ma == null || ma.length == 0 || ma[0].length == 0 || ma[0][0] == 1 || ma[ma.length - 1][ma[0].length - 1] == 1) {
                return null;
            }
            
            int[][] map = new int[ma.length][ma[0].length];
            Queue<Integer> rq = new LinkedList<Integer>();
            Queue<Integer> cq = new LinkedList<Integer>();
            Queue<Node> res = new LinkedList<Node>();
            map[0][0] = 1;
            rq.add(0);
            cq.add(0);
            int r = 0;
            int c = 0;
            while (!rq.isEmpty()) {
                r = rq.poll();
                c = cq.poll();
                res.add(new Node(r, c));
                if (r == ma.length - 1 && c == ma[0].length - 1) {
                    return res;
                }
                walkTo(r, c, r - 1, c, ma, map, rq, cq);//up
                walkTo(r, c, r + 1, c, ma, map, rq, cq);//down
                walkTo(r, c, r, c - 1, ma, map, rq, cq);//left
                walkTo(r, c, r, c + 1, ma, map, rq, cq);//right
            }
            return null;
        }
        public static void walkTo(int fromR, int fromC, int toR, int toC, int[][] ma, int[][] map, Queue<Integer> rq, Queue<Integer> cq) {
            if (toR < 0 || toR >= ma.length || toC < 0 || toC >= ma[0].length || ma[toR][toC] == 1 || map[toR][toC] != 0) {
                return;
            }
            map[toR][toC] = map[fromR][fromC] + 1;
            rq.add(toR);
            cq.add(toC);
        }
    }
    class Node {
        int r;
        int c;
        public Node(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

[20180605172443514]: /images/20220523/ed9e7bc7a25841c4adb6202f805f5e99.png