1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4#include <string.h>
5
6typedef struct {
7    int position;
8    int moves;
9} QueueNode;
10
11typedef struct {
12    QueueNode* nodes;
13    int front;
14    int rear;
15    int capacity;
16} Queue;
17
18Queue* createQueue(int capacity) {
19    Queue* queue = (Queue*)malloc(sizeof(Queue));
20    queue->capacity = capacity;
21    queue->front = queue->rear = 0;
22    queue->nodes = (QueueNode*)malloc(capacity * sizeof(QueueNode));
23    return queue;
24}
25
26bool isQueueEmpty(Queue* queue) {
27    return queue->front == queue->rear;
28}
29
30void enqueue(Queue* queue, int position, int moves) {
31    queue->nodes[queue->rear++] = (QueueNode){position, moves};
32}
33
34QueueNode dequeue(Queue* queue) {
35    return queue->nodes[queue->front++];
36}
37
38int snakesAndLadders(int** board, int boardSize, int* boardColSize) {
39    int n = boardSize;
40    int *flattenBoard = (int *)malloc((n * n + 1) * sizeof(int));
41    int index = 1;
42    bool flip = false;
43    for (int i = n - 1; i >= 0; i--) {
44        if (flip) {
45            for (int j = n - 1; j >= 0; j--) {
46                flattenBoard[index++] = board[i][j];
47            }
48        } else {
49            for (int j = 0; j < n; j++) {
50                flattenBoard[index++] = board[i][j];
51            }
52        }
53        flip = !flip;
54    }
55
56    bool *visited = (bool *)calloc(n * n + 1, sizeof(bool));
57    Queue* queue = createQueue(n * n);
58    enqueue(queue, 1, 0);
59    visited[1] = true;
60
61    while (!isQueueEmpty(queue)) {
62        QueueNode node = dequeue(queue);
63        int pos = node.position;
64        int moves = node.moves;
65
66        for (int i = 1; i <= 6; i++) {
67            int nextPos = pos + i;
68            if (nextPos <= n * n) {
69                if (flattenBoard[nextPos] != -1) {
70                    nextPos = flattenBoard[nextPos];
71                }
72                if (!visited[nextPos]) {
73                    if (nextPos == n * n) {
74                        free(flattenBoard);
75                        free(visited);
76                        free(queue->nodes);
77                        free(queue);
78                        return moves + 1;
79                    }
80                    visited[nextPos] = true;
81                    enqueue(queue, nextPos, moves + 1);
82                }
83            }
84        }
85    }
86    free(flattenBoard);
87    free(visited);
88    free(queue->nodes);
89    free(queue);
90    return -1;
91}

1#include <queue>

using namespace std;

int snakesAndLadders(vector<vector<int>>& board) {
    int n = board.size();
    vector<int> dist(n * n + 1, INT_MAX);
    vector<int> flattenBoard(n * n + 1, -1);
    int idx = 1;
    bool leftToRight = true;
    for (int i = n - 1; i >= 0; --i) {
        if (leftToRight) {
            for (int j = 0; j < n; ++j) {
                flattenBoard[idx++] = board[i][j];
            }
        } else {
            for (int j = n - 1; j >= 0; --j) {
                flattenBoard[idx++] = board[i][j];
            }
        }
        leftToRight = !leftToRight;
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, 1});
    dist[1] = 0;

    while (!pq.empty()) {
        auto [current_dist, u] = pq.top(); pq.pop();
        if (u == n * n) return current_dist;

        for (int dice = 1; dice <= 6; ++dice) {
            int v = u + dice;
            if (v <= n * n) {
                v = flattenBoard[v] != -1 ? flattenBoard[v] : v;
                if (current_dist + 1 < dist[v]) {
                    dist[v] = current_dist + 1;
                    pq.push({dist[v], v});
                }
            }
        }
    }

    return -1;
}