main.c
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
#include <stdio.h> #include <stdlib.h> #include <limits.h> int main () { int T; scanf ("%d", &T); while (T--) { int num_snakes, num_ladders; scanf ("%d,%d", &num_snakes, &num_ladders); int num_links = num_snakes + num_ladders; int * board = malloc (101 * sizeof(int)); for (int i = 0; i <= 100; ++i) board[i] = i; for (int i = 0; i != num_links; ++i) { int from, to; scanf ("%d,%d", &from, &to); board[from] = to; } #if DEBUG printf ("board:\n"); for (int i = 0; i <= 100; ++i) if (board[i] != i) printf ("%d -> %d\n", i, board[i]); printf ("\n"); #endif int * moves_to_finish = malloc (101 * sizeof(int)); for (int i = 0; i != 100; ++i) moves_to_finish[i] = INT_MAX; moves_to_finish[100] = 0; short changed; do { changed = 0; for (int i = 99; i >= 0; --i) for (int roll = 1; roll <= 6 && i + roll <= 100; ++roll) { int destination = board[i+roll]; if (moves_to_finish[destination] < moves_to_finish[i] - 1) { moves_to_finish[i] = moves_to_finish[destination] + 1; changed = 1; } } } while (changed != 0); #if DEBUG for (int i = 0; i <= 100; ++i) printf ("from %d: %d\n", i, moves_to_finish[i]); #endif #if DEBUG printf ("min moves: %d\n\n", moves_to_finish[0]); #else printf ("%d\n", moves_to_finish[0]); #endif free (board); free (moves_to_finish); } return 0; } |
