【LeetCode教學】909. Snakes and Ladders

BFS, C++, Cpp, LeetCode, queue, unordered_set

給定一個棋盤，棋盤上有蛇或梯子，計算從起點抵達終點的最小行動次數。

題目連結：連結點此。

題目描述

給定一個 n x n 的整數矩陣棋盤，棋盤上的單元格從棋盤左下角（ board[n – 1][0]）開始，以之字形的方式從 1 到 n2 編號標記。

從棋盤的格子1開始，用擲骰子（結果為 1 到 6）來決定往前走幾步，如果目標格子有蛇或梯子，則必須移動到蛇或梯子的目的地。

  • board[i][j] = -1 表示格子無蛇或梯子。
  • board[i][j] = k 表示格子有蛇或梯子，移動到格子 k。

每次擲骰子最多只能走一次蛇或梯子，如果蛇或梯子的終點是另一條蛇或梯子的起點，則無需跟隨後續的蛇或梯子。

返回到終點（格子 n2 ）所需的最少擲骰子次數。

如果無法到達該終點，則傳回 -1。

題目限制

  • n == board.length == board[i].length
  • 2 <= n <= 20
  • board[i][j] is either -1 or in the range [1, n2].
  • The squares labeled 1 and n2 are not the starting points of any snake or ladder.

解題方法

這道題是一個圖論問題，可以將棋盤視為一個有向圖，格子為節點，擲骰子和蛇/梯子為邊，邊的權重為 1（每次移動算一步）。目標是找到從格子 1 到格子 n² 的最短路徑（最少移動次數）。由於需要最短路徑，且邊的權重均為 1，廣度優先搜尋（BFS） 是最合適的解法。

1. 前置作業

首先取得取得board的大小（題目表示row和column數量相同，是個正方形的棋盤呢），方便後續計算：

int n = board.size();

為了使用BFS演算法，我們需要宣告以下變數：

  • queue用來記錄每次移動時的{當前位置,已移動次數}。
  • unordered_set用來記錄已經訪問過的格子，避免走入迴圈。
queue<pair<int, int>> q;  
unordered_set<int> visited;

開始BFS演算法前先做初始化、給初始值：從格子1開始走，同時將格子1標記為已訪問。

q.push({1, 0});
visited.insert(1);

2. BFS演算法

使用 BFS 按層次探索所有可能的格子。

while (q.empty() == false)
{
}

首先用pair結構化綁定取出當前位置和已移動次數。

auto [currentPosition, step] = q.front();
q.pop();

模擬擲骰子點數1~6：

for (int i = 1; i <= 6; i++)
{
}

分析每次擲骰子的結果：

按照骰子點數往前走後的新位置

int newPosition = currentPosition + i;

將新位置的格子編號（1 到 n²）轉換為棋盤座標 (row, column)

int row = n - ((newPosition - 1) / n) - 1;
int column;
if (row % 2 != n % 2) column = ((newPosition - 1) % n);  //順向
else column = (n - 1) - ((newPosition - 1) % n);  //逆向

如果在新位置有梯子或蛇，則直接前往梯子或蛇的另一端。

if (board[row][column] != -1) newPosition = board[row][column];

檢查是否已經抵達終點

if (newPosition >= n * n) return step + 1;

檢查如果newPosition這個點還沒有訪問過，那就將這個點加入queue讓後續的while迴圈繼續遍歷。

if (visited.find(newPosition) == visited.end())
{
    q.push({newPosition, step + 1});
    visited.insert(newPosition);
}

3. BFS演算法結束後，如果還是無法走到終點，依照題目要求返回-1。

return -1;

完整程式碼

class Solution {
public:
    int snakesAndLadders(vector<vector<int>>& board) {

        //1. 前置作業
        int n = board.size();  //取得board有多大（題目表示row和column相同）
        queue<pair<int, int>> q;  //使用queue記錄每次移動的{當前位置,已移動次數}
        unordered_set<int> visited;  //記錄已經訪問過的格子，避免走入迴圈
        q.push({1, 0});  //從格子1開始走
        visited.insert(1);  //將格子1標記為已訪問

        //2. BFS演算法
        while (q.empty() == false)
        {
            //取出當前位置和已移動次數
            auto [currentPosition, step] = q.front();
            q.pop();

            //模擬擲骰子點數1~6
            for (int i = 1; i <= 6; i++)
            {
                //按照骰子點數往前走後的新位置
                int newPosition = currentPosition + i;

                //計算新位置對應到的座標(row和column)
                int row = n - ((newPosition - 1) / n) - 1;
                int column;
                if (row % 2 != n % 2) column = ((newPosition - 1) % n);  //順向
                else column = (n - 1) - ((newPosition - 1) % n);  //逆向

                //如果在新位置有梯子或蛇
                if (board[row][column] != -1) newPosition = board[row][column];

                //檢查是否已經抵達終點
                if (newPosition >= n * n) return step + 1;

                //將新位置加入queue讓後續的while迴圈繼續遍歷
                if (visited.find(newPosition) == visited.end())  //如果還沒有訪問過newPosition這個點
                {
                    //將新位置加入queue
                    q.push({newPosition, step + 1});

                    //將當前格子標記為已訪問
                    visited.insert(newPosition);
                }
            }
        }

        //3. 如果無法走到終點
        return -1;
    }
};

測試資料

有梯子和蛇的棋盤，而且是往回走可能會比一直往前走更快抵達終點的情形（最佳解需要從格子17的梯子退回格子13）。

我試過貪婪演算法解這題但就是卡在這種case，果然還是用BFS演算法才能考慮到全局最佳解。

Input: board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]
Output: 4

棋盤很小、不走梯子反而會更快抵達終點的case。

不走梯子的話骰子3點可以1步就走到終點，走梯子的話反而總共需要2步（先走梯子到格子3、再走1步到終點格子4）。

Input: board = [[-1,-1],[-1,3]]
Output: 1

測試如果沒有任何梯子而且格子數量很多時，會不會觸發Time Limit Exceeded。

Input: board = [[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1]]
Output: 67

一條蛇或梯子的終點是另一條蛇或梯子。

Input: board = [[-1,4],[-1,3]]
Output: 1

時間與空間複雜度

時間複雜度：O(n²)，每個格子最多訪問一次，每個格子有最多 6 種可能（擲骰子 1 到 6）。

空間複雜度：O(n²)，用於queue和unordered_set。

其他相關題目

  • 130. Surrounded Regions
  • 200. Number of Islands
  • 695. Max Area of Island

相關文章

返回頂端