505. The Maze II

原题链接：https://leetcode.com/articles/the-maze-ii/

我的思路

在做完了第一道迷宫问题 http://www.cnblogs.com/optor/p/8533068.html 后，这第二道迷宫问题就比较简单了。

题意是求最短路径，所以我觉得使用深度优先搜索不合适（因为深度优先搜索需要遍历完所有走法之后再取路径最短的，比较麻烦），而广度优先搜索则较为适合这个问题。所以我尝试写了下广度优先搜索的实现：

import java.util.LinkedList;

import java.util.Queue;

/**

 * Created by clearbug on 2018/2/26.

 */

public class Solution {

    public static void main(String[] args) {

        Solution s = new Solution();

        /**

         * 0 0 1 0 0

         0 0 0 0 0

         0 0 0 1 0

         1 1 0 1 1

         0 0 0 0 0

         */

        int[][] board = {

                {0, 0, 1, 0, 0},

                {0, 0, 0, 0, 0},

                {0, 0, 0, 1, 0},

                {1, 1, 0, 1, 1},

                {0, 0, 0, 0, 0},

        };

        System.out.println(s.hasPath(board, new int[]{0, 4}, new int[]{4, 4}));

        /**

         * 0 0 1 0 0

         0 0 0 0 0

         0 0 0 1 0

         1 1 0 1 1

         0 0 0 0 0

         */

        int[][] board2 = {

                {0, 0, 1, 0, 0},

                {0, 0, 0, 0, 0},

                {0, 0, 0, 1, 0},

                {1, 1, 0, 1, 1},

                {0, 0, 0, 0, 0},

        };

        System.out.println(s.hasPath(board2, new int[]{0, 4}, new int[]{3, 2}));

    }

    public int hasPath(int[][] maze, int[] start, int[] dest) {

        maze[start[0]][start[1]] = 2;

        int[][] dirs = {

                {0, 1},

                {0, -1},

                {-1, 0},

                {1, 0}

        };

        Queue<int[]> queue = new LinkedList<>();

        queue.add(start);

        while (!queue.isEmpty()) {

            int[] s = queue.remove();

            if (s[0] == dest[0] && s[1] == dest[1]) {

                return maze[s[0]][s[1]] - 2;

            }

            for (int[] dir : dirs) {

                int x = s[0] + dir[0];

                int y = s[1] + dir[1];

                while (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] != 1) {

                    x += dir[0];

                    y += dir[1];

                }

                if (maze[x - dir[0]][y - dir[1]] == 0) {

                    queue.add(new int[]{x - dir[0], y - dir[1]});

                    maze[x - dir[0]][y - dir[1]] = maze[s[0]][s[1]] + Math.abs(x - dir[0] - s[0]) + Math.abs(y - dir[1] - s[1]);

                }

            }

        }

        return -1;

    }

}

直接在上一题的广度优先搜索算法实现上修改就行啦！！！下面去看看官方的解法是怎样的吧！

官方方法一：深度优先搜索

这次就不抄代码了，只想说官方提供的答案就是思路清晰，代码简介！

官方方法二：广度优先搜索

感觉这里的广度优先搜索算法实现里面稍微有点不妥啊，貌似还不如我的实现呢哈哈

官方方法三：使用迪杰斯特拉算法

把求图的最短距离的迪杰斯特拉算法用在了这里，迪杰斯特拉算法我也是看了大半天才看懂了。官方的实现又是看了半天看懂了，就不写了，有点复杂啊！

学习迪杰斯特拉算法：https://www.youtube.com/watch?v=F728NKEeODQ

官方方法四：迪杰斯特拉算法+优先级队列

在方法三的基础上使用优先级队列进行了优化，迪杰斯特拉算法对于目前的我来说就够复杂了，再加上优先级队列。。。代码实现基本上是看懂了，所以先这样吧！

巴特西