0909.cpp (1095B)
1 class Solution { 2 public: 3 int snakesAndLadders(vector<vector<int>> &board) { 4 const int n = board.size(); 5 6 // index directy with a square instead of a coordinate 7 vector<int> cord(n * n + 1); 8 9 int crnt = 1, x = n - 1, y = 0, dir = 1; 10 while (crnt <= n * n) { 11 cord[crnt] = board[x][y]; 12 if (crnt % n == 0) 13 x--, dir *= -1; 14 else 15 y += dir; 16 crnt++; 17 } 18 19 vector<bool> visited(n * n + 1); 20 queue<pair<int, int>> q; 21 int res = INT_MAX; 22 23 q.push({1, 0}), visited[1] = true; 24 while (!q.empty()) { 25 auto [crnt, move] = q.front(); 26 q.pop(); 27 28 if (crnt == n * n) return move; 29 30 for (int i = 0; i < 6; i++) { 31 if (++crnt > n * n) break; 32 int square = cord[crnt] == -1 ? crnt : cord[crnt]; 33 if (visited[square]) continue; 34 visited[square] = true; 35 q.push({square, move + 1}); 36 } 37 } 38 return -1; 39 } 40 };