leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0909.cpp (1095B)

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