本文共 1987 字，大约阅读时间需要 6 分钟。

题目描述:一个二维矩阵由0和1构成,求从左上角跑到右下角的最短路径。

解法：广度优先遍历，使用队列，队列中的元素如果不弹出的话，从队头到队尾是步数一次增加，

即:走一步可以到达的节点、走两步可以达到的节点、......

要设置已访问数组:目的是防止某个节点重复入队，因为如果某个元素被第二次访问，那此次走到它的步数一定大于第一次走到它的步数，所以这个节点不符合最短路径，所以没必要入队，而且这个算法的循环条件是队列不为空，如果可以重复入队，那么有可能出现队列永远不为空的情况，就比如说如果矩阵中存在环路。

package Array;import java.util.LinkedList;import java.util.Queue;public class MinRoad {    public static int minRoad(int[][] arr){        if(arr == null || arr.length == 0 || arr[0].length == 0 || arr[0][0] == 0){            return 0;        }        //寻找最小路径时使用广度优先遍历得将访问过的地方置为1,因为最先访问某点肯定是到达该点步数最少的。以后就即使有点        //再来到该点，也不可能是最短路径1        int[][] go = {
  {0,-1},{-1,0},{0,1},{1,0}};        Queue
   
     qu = new LinkedList<>();        Node node = new Node(0,0,1);        qu.add(node);        boolean[][] visited = new boolean[arr.length][arr[0].length];        visited[0][0] = true;        while(!qu.isEmpty()){            Node tmp = qu.poll();            int nowRow = tmp.row;            int nowCol = tmp.col;            int nowStep = tmp.step;            if(nowRow == arr.length - 1 && nowCol == arr[0].length - 1){                return nowStep;            }            for(int i = 0; i < 4; i++){                int nextRow = nowRow + go[i][0];                int nextCol = nowCol +go[i][1];                if(nextRow >= 0 && nextRow < arr.length && nextCol >= 0 && nextCol < arr[0].length                        && arr[nextRow][nextCol] == 1 && !visited[nextRow][nextCol]){                    Node node1 = new Node(nextRow,nextCol,nowStep + 1);                    qu.add(node1);                    visited[nextRow][nextCol] = true;                }            }        }        return 0;    }    public static void main(String[] args){        int[][] arr = {
  {1,0,1,1,1},{1,0,1,0,1},{1,1,1,0,1},{0,0,0,0,1}};        System.out.print(minRoad(arr));    }}class Node{    int row;    int col;    int step;    public Node(int row, int col, int step){        this.row = row;        this.col = col;        this.step = step;    }}
   

转载地址：http://pnzji.baihongyu.com/