LeetCode 1210. 穿過迷宮的最少移動次數（狀態壓縮BFS）

1. 題目

你還記得那條風靡全球的貪吃蛇嗎？

我們在一個 n*n 的網格上構建了新的迷宮地圖，蛇的長度為 2，也就是說它會佔去兩個單元格。
蛇會從左上角（(0, 0) 和 (0, 1)）開始移動。
我們用 0 表示空單元格，用 1 表示障礙物。
蛇需要移動到迷宮的右下角（(n-1, n-2) 和 (n-1, n-1)）。

每次移動，蛇可以這樣走：

• 如果沒有障礙，則向右移動一個單元格。並仍然保持身體的水平／豎直狀態。

• 如果沒有障礙，則向下移動一個單元格。並仍然保持身體的水平／豎直狀態。

• 如果它處於水平狀態並且其下面的兩個單元都是空的，就順時針旋轉 90 度。蛇從（(r, c)、(r, c+1)）移動到 （(r, c)、(r+1, c)）。
  

• 如果它處於豎直狀態並且其右面的兩個單元都是空的，就逆時針旋轉 90 度。蛇從（(r, c)、(r+1, c)）移動到（(r, c)、(r, c+1)）。
  

返回蛇抵達目的地所需的最少移動次數。

如果無法到達目的地，請返回 -1。

範例 1：

輸入：grid = [[0,0,0,0,0,1],
               [1,1,0,0,1,0],
               [0,0,0,0,1,1],
               [0,0,1,0,1,0],
               [0,1,1,0,0,0],
               [0,1,1,0,0,0]]
輸出：11
解釋：
一種可能的解決方案是 
[右, 右, 順時針旋轉, 右, 下, 下, 下, 下, 逆時針旋轉, 右, 下]。

範例 2：
輸入：grid = [[0,0,1,1,1,1],
               [0,0,0,0,1,1],
               [1,1,0,0,0,1],
               [1,1,1,0,0,1],
               [1,1,1,0,0,1],
               [1,1,1,0,0,0]]
輸出：9
 
提示：
2 <= n <= 100
0 <= grid[i][j] <= 1
蛇保證從空單元格開始出發。

來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/minimum-moves-to-reach-target-with-rotations
著作權歸領釦網路所有。商業轉載請聯絡官方授權，非商業轉載請註明出處。

2. 解題

• 把尾巴的座標 x,y 還有方向 d，三個資訊編碼成101進位制數
• 然後蛇可以三種走法：前進、整體平移、繞尾巴旋轉

class Solution {
    vector<vector<int>> dir = {{0,1}, {1,0}};
    int n;
public:
    int minimumMoves(vector<vector<int>>& grid) {
        n = grid.size();
        if(grid[n-1][n-2] || grid[n-1][n-1])
            return -1;
        int state, nt, pos, d, nd, i, j, k, x, y, x1, y1, x2, y2;
        queue<int> q;
        //將xy座標壓縮為一個數，再乘以 101，+ 方位，全部壓縮為一個數
        unordered_set<int> vis;
        q.push(0);// pos = (101*i + j)*101 + dir
        int step = 0, size;
        int target = (101*(n-1)+(n-2))*101;
        while(!q.empty())
        {
            size = q.size();
            while(size--)
            {
                state = q.front();
                q.pop();
                if(state == target)
                    return step;
                d = state%101;
                pos = state/101;
                i = pos/101;//原來尾巴位置
                j = pos%101;
                // cout << " i :" << i << " j: " << j << " d : " << d << endl;
                x = i+dir[d][0];//原來頭的位置
                y = j+dir[d][1];

                // 直行，方向不變
                x1 = i+dir[d][0];//下一個尾巴佔據的位置
                y1 = j+dir[d][1];
                x2 = x+ dir[d][0];//下一個頭的位置
                y2 = y+ dir[d][1];
                nt = (101*x1+y1)*101+d;//下一個狀態
                if(ok(x2, y2) && grid[x2][y2]== 0
                    && !vis.count(nt))
                {
                    vis.insert(nt);
                    q.push(nt);//下一個狀態
                }
                // 平移，方向不變
                nd = d == 0 ? 1 : 0;
                x1 = i+dir[nd][0];//下一個尾巴佔據的位置
                y1 = j+dir[nd][1];
                x2 = x+ dir[nd][0];//下一個頭的位置
                y2 = y+ dir[nd][1];
                nt = (101*x1+y1)*101+d;//下一個狀態
                if(ok(x1, y1) && grid[x1][y1]==0 
                    && ok(x2, y2) && grid[x2][y2]== 0
                    && !vis.count(nt))
                {
                    vis.insert(nt);
                    q.push(nt);
                }
                // 旋轉，方向變化, 尾巴位置沒變
                nt = state/101*101 + nd;//下一個位置的編碼
                if(ok(x1, y1) && grid[x1][y1]==0 
                    && ok(x2, y2) && grid[x2][y2]== 0
                    && !vis.count(nt))
                {
                    vis.insert(nt);
                    q.push(nt);
                }
            }
            step++;
        }
        return -1;
    }
    bool ok(int x, int y)
    {
        return x>=0 && x < n && y>=0 && y<n;
    }
};

132 ms 17.5 MB

---

我的CSDN部落格地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！