leetcode

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 };