909.md

909. Snakes and Ladders

Solution 1 (time O(n^2), space O(n^2))

class Solution {
public:
    int snakesAndLadders(vector<vector<int>>& board) {
        int n = board.size();
        queue <pair <int, int>> q;
        q.push(make_pair(1, 0));
        vector<bool> vis(n * n + 1, false);
        vis[1] = true;
        while (!q.empty()) {
            pair <int, int> cur_pair = q.front();
            q.pop();
            int cur_state = cur_pair.first;
            int cur_level = cur_pair.second;
            int new_state, new_r, new_c;
            for (int i = 1; i <= 6; i++) {
                new_state = cur_state + i;
                new_r = (new_state - 1) / n;
                new_c = (new_state - 1) % n;
                if (new_r % 2 == 1){
                    new_c = n - 1 - new_c;
                }
                new_r = n - 1 - new_r;
                if (board[new_r][new_c] != -1) {
                    new_state = board[new_r][new_c];
                }
                if (new_state == n * n) {
                    return cur_level + 1;
                }
                if (vis[new_state] == false) {
                    vis[new_state] = true;
                    q.push(make_pair(new_state, cur_level + 1));
                }
            }
        }
        return -1;
    }
};