---
# System prepended metadata

title: 909. Snakes and Ladders
tags: [Leetcode]

---

<style>
    html, body, .ui-content {
    background: #222222;
    color: #00BFFF;
}
    /* 設定 code 模板 */
    .markdown-body code,
.markdown-body tt {
    background-color: #ffffff36;
}
.markdown-body .highlight pre,
.markdown-body pre {
    color: #ddd;
    background-color: #00000036;
}
.hljs-tag {
    color: #ddd;
}
.token.operator {
  background-color: transparent;
}    
/* 設定連結 */
a,
.open-files-container li.selected a {
    color: #89FFF8;
    
}
a:hover,
.open-files-container li.selected a:hover {
    color: #89FFF890;
}
   
</style>

###### tags: `Leetcode`

# 909. Snakes and Ladders

###### Link : https://leetcode.com/problems/snakes-and-ladders/description/

## 題目
回傳由起點走到終點的最短路徑
## 程式碼 I
```cpp=
class Solution {
public:
    int snakesAndLadders(vector<vector<int>>& board) {
        const int n = board.size(), end = pow(n, 2);
        vector<int> Board;
        Board.push_back(0);
        for(int i = n-1, j = 0;i >= 0;i--, j++){
            if(j & 1)
                Board.insert(Board.end(), board[i].rbegin(), board[i].rend());
            else
                Board.insert(Board.end(), board[i].begin(), board[i].end());
        }
        vector<int> dist(n * n + 1, -1);
        queue<int> Queue;
        dist[1] = 0;
        Queue.push(1);
        while(!Queue.empty()){
            int cur = Queue.front();
            Queue.pop();
            for(int j = 1;j <= 6;j++){
                if(cur + j > end) break;
                int dest = (Board[cur + j] == -1)?cur + j:Board[cur + j];
                if(dist[dest] == -1){
                    dist[dest] = dist[cur] + 1;
                    Queue.push(dest);
                }
            }
        }
        return dist[end];
    }
};
```
## Date 
2023/1/24