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}

1var