廣度優(yōu)先+雙分裂蛇

雙分裂蛇：是求二維表中從起點到終點的經(jīng)典思路（也是求無權(quán)圖的最短路徑問題的經(jīng)典解法）。創(chuàng)建兩條分裂蛇，分別從起點和終點出發(fā)，兩者相遇，則找到一條路徑。時間復(fù)雜度理論上和單分裂蛇一樣，但實際效率雙分裂蛇更高。

1. 分裂蛇的意思是：如果遇到分叉路，分裂蛇A可以分裂成對應(yīng)數(shù)量的蛇，然后分頭行動。
2. 為什么雙分裂蛇更快？因為只有一條蛇時，最壞情況下所有結(jié)點都走一遍才能找到最短路徑
3. 而雙分裂蛇，無論分裂多少，肯定是最短路徑上的兩條蛇最先相遇。所以兩條蛇初次相遇的路徑，就是最短路徑。而不用像單分裂蛇那樣，很有可能將所有路走一遍再比較才能知道哪條路最短。

簡單來說，單分裂蛇，它需要走的步數(shù)更多，因為它要自己從起點走到終點，因此分裂的蛇也就越多，訪問的結(jié)點也就越多。
而雙分裂蛇，兩條蛇走的步數(shù)都是單分裂蛇的一半。所以兩條蛇分裂的蛇會很少。訪問的結(jié)點就少

舉個例子，一張可以無限對折的0.0002米厚的紙，對折40次左右可以到月球，40次正好就是219902公里。而對折40次的一半左右，比如23次只有1.677公里。此時我搞兩張紙各對折40次的一半，加起來是1.677+1.677 = 3.3公里左右

可見，219902公里是一張紙對折40次的結(jié)果。3.3公里左右是兩張紙對折40次一半20次左右的結(jié)果. 而回到分裂蛇的例子。一條蛇分裂40次，和兩條蛇各分裂20次。誰訪問的結(jié)點更少呢？

因此理論上，最壞情況下雙分裂蛇和單分裂蛇都是n^2的時間復(fù)雜度，也就是每個結(jié)點訪問兩次，但是實際上，找最短路徑，就和一張紙對折40次和兩張紙對折20次的區(qū)別是一樣的，只要路徑足夠長，雙分裂蛇訪問的結(jié)點個數(shù)，和單分裂蛇訪問的結(jié)點個數(shù)根本不是一個量級,就像一張紙對折40次上月球，兩張紙對折20次加起來走不出一個小區(qū)是一個道理。雙分裂蛇的效率是比單分裂蛇高的。

但是無論單分裂蛇還是雙分裂蛇，找最短路徑，都滿足：初次相遇的蛇所在路徑為最短路徑。

也就是，就算是單分裂蛇，也不需要所有路徑走一遍統(tǒng)計路徑長度，才能找出最短的
因為最短路徑上的蛇一定會先最先到達(dá)。（前提是所有蛇的速度一樣，都是大家一起一步一步走）文章來源地址http://www.zghlxwxcb.cn/news/detail-858402.html

1. 創(chuàng)建兩個隊列A和B，當(dāng)做分裂蛇，分別從起點[0][0]和終點[n-1][n-1]出發(fā)，將兩個結(jié)點分別入各自的隊列
2. A隊列先走一步，情況允許就分裂。新分裂出的蛇不額外走

1. 一步的含義是，我可以向8個方向走，只要能走就走。
2. 分裂：如果多個方向都滿足條件，則進(jìn)行分裂，讓分裂的蛇到達(dá)指定地點（一步）,然后將分裂的蛇全部入隊列
3. 但是新入隊列的蛇，不可以繼續(xù)處理，因為它們已經(jīng)走了一步了

3. 如果兩個隊列沒有相遇，B隊列也走一步，情況允許就分裂，新分裂的不走
4. 直到兩個隊列中有蛇相遇，就結(jié)束程序。因為雙分裂蛇的特點就是，最先相遇的兩條蛇所在路徑為最短路徑

1. 雙分裂蛇版本用時6ms
   

class Solution {
    final static int[] dx = {1, 1, 1, 0, 0, -1, -1, -1};//右下，下，左下，右，左，右上，上，左上
    final static int[] dy = {1, 0, -1, 1, -1, 1, 0, -1};//右下，下，左下，右，左，右上，上，左上
    final static int SIGN_A = 2;//A隊列走過的路的標(biāo)識
    final static int SIGN_B = 3;//B隊列走過的路的標(biāo)識
    class Node {//隊列中的結(jié)點，保存x和y坐標(biāo)
        int x, y;
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length;
        if(grid[0][0] == 1 || grid[n-1][n-1] == 1) return -1;
        else if(grid[0][0] == 0 && n == 1) return 1;

        int steps = 2;//走了多少步，兩個隊列(貪吃蛇)一起算
        //頭尾隊列，一個從頭走，一個從尾巴走，兩個隊列相遇，就是一個答案
        Queue<Node> headQue = new LinkedList<Node>();
        Queue<Node> tailQue = new LinkedList<Node>();
        headQue.offer(new Node(0, 0));
        tailQue.offer(new Node(n-1, n-1));

        grid[0][0] = SIGN_A;
        grid[n-1][n-1] = SIGN_B;
        //兩個隊列一起走
        while(!headQue.isEmpty() && !tailQue.isEmpty()) {
            boolean encounter = nextStep(grid, headQue, SIGN_A);//A隊列走一步，是否相遇B隊列
            if(encounter) return steps;//如果相遇，則返回步數(shù)
            //沒有相遇，則A隊列步數(shù)+1
            steps++;
            //B隊列走一步，是否相遇A隊列
            encounter = nextStep(grid, tailQue, SIGN_B);
            if(encounter) return steps;
            steps++;
        }
        return -1;//如果一直沒有相遇就返回-1
    }
    //走一步
    private boolean nextStep(int [][]grid, Queue<Node> que, int sign) {
        int n = grid.length;
        int size = que.size();
        while((size--) > 0) {//如果當(dāng)前隊列有結(jié)點（無論多少個），那么這些結(jié)點只走一步，不多走，也就是這些結(jié)點走了一步后，過程中新添加的結(jié)點，本次不考慮
            Node cur = que.poll();//出隊列當(dāng)前結(jié)點
            int x = cur.x, y = cur.y;//獲取其坐標(biāo)
            for(int i = 0; i < 8; ++i) {//8個方向按右下，下，左下，右，左，右上，上，左上的順序走一下
                int nx = x + dx[i];
                int ny = y + dy[i];
                //如果下標(biāo)越界，或者要走的這一方向==1（此路不通），或者要走的這一方向當(dāng)前隊列已經(jīng)走過了grid[nx][ny] == sign，就跳過
                if(nx < 0 || nx >= n || ny < 0 || ny >= n || grid[nx][ny] == 1 || grid[nx][ny] == sign) continue;
                // 如果要走的方向遇到了另一個隊列，則說明相遇
                if(grid[nx][ny] != 0) return true;//返回true
                //如果沒有相遇，向當(dāng)前方向走一步
                grid[nx][ny] = sign;
                que.add(new Node(nx, ny));//添加到隊列繼續(xù)
            }
        }
        return false;
    }
}

2. 單分裂蛇版本，用時10ms
   

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        if(grid[0][0] != 0)return -1;
        if(grid.length == 1){
            if(grid[0][0] == 0) return 1;
            else return -1;
        }
        int[] dx = {-1, -1, -1, 0,  0, 1, 1, 1};
        int[] dy = {-1, 0, 1, -1, 1, -1, 0,1};
        int n = grid.length;
        // 記錄坐標(biāo)
        Queue<int[]> queue = new LinkedList();//單分裂蛇
        queue.offer(new int[]{0,0});//從起點開始
        grid[0][0] = 1;//走過的就標(biāo)志為1
        int length = 0;//路徑長度
        loop:while(queue.size() > 0){//如果還有分裂蛇存在
            int size = queue.size();//獲取當(dāng)前分裂蛇，這些分裂蛇可以進(jìn)行分裂，然后走一步
            ++length;//走一步+1個路徑長度
            while((size--) > 0){//只有當(dāng)前分裂蛇可以走一步，多條路可走就分裂，新的分裂蛇不可以走，如果使用queue.size()會將新的分裂蛇也處理了
                int[] pos = queue.poll();//依次獲取這些現(xiàn)在存在的分裂蛇
                for(int i =0; i < 8; i++){//從8個方向走
                    int x = pos[0] + dx[i];
                    int y = pos[1] + dy[i];
                    //如果這個方向可以走，并且沒有分裂蛇走過
                    if(x >=0 && y >= 0 && x < grid.length && y < grid.length && grid[x][y] == 0){
                        queue.offer(new int[]{x,y});//就分裂一條蛇過去，這條分裂后新進(jìn)入隊列的蛇，本次不可以再處理
                        grid[x][y] = length +1;//將此結(jié)點標(biāo)志為已到達(dá)過，賦值為：路徑長度+1
                        //這里很重要，終點一定是最短路徑的蛇先到，此時它會將這個結(jié)點標(biāo)志為已到訪過
                        //后面在較長路徑的蛇，不會覆蓋這個值
                        //如果當(dāng)前分裂蛇是第一個到終點的，則他就是最短路徑上的蛇
                        if(x == grid.length-1 && y == grid.length-1) break loop;//跳出整個循環(huán)，不繼續(xù)處理任何蛇
                    }
                }
            }
        }
        return grid[n-1][n-1] <2 ? -1 : grid[n-1][n-1];//返回到終點的最短路徑長度
    }
}

到了這里，關(guān)于java數(shù)據(jù)結(jié)構(gòu)與算法刷題-----LeetCode1091. 二進(jìn)制矩陣中的最短路徑的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！