Source code for submission s574

grasshop.cpp

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4.  
  5. #define MAKE_QUEUE(name, sz, value_type) \
  6. struct {size_t size; size_t start; size_t stop; value_type *vals; } name; \
  7. name.size = sz + 1; \
  8. name.start = sz; \
  9. name.stop = 0; \
  10. name.vals = (value_type*) malloc(sizeof(value_type) * name.size);
  11.  
  12. #define enq(name, val) \
  13. (name.vals[name.stop] = val, name.stop = (name.stop + 1) % name.size)
  14.  
  15. #define deq(name) \
  16. (name.start = (name.start + 1) % name.size, name.vals[name.start])
  17.  
  18. #define empty(name) \
  19. ((name.start + 1) % name.size == name.stop)
  20.  
  21. typedef struct {
  22. int node;
  23. int distance;
  24. } dijkstra_node;
  25.  
  26. int key(dijkstra_node n) {
  27. return -n.distance;
  28. }
  29.  
  30. template <typename G>
  31. void dijkstra(G graph, int start, int end) {
  32. MAKE_QUEUE(queue, vertices(graph), dijkstra_node);
  33.  
  34. dijkstra_node node = {start, 0};
  35. enq(queue, node);
  36.  
  37. while (!empty(queue)) {
  38. node = deq(queue);
  39.  
  40. if (node.node == end) {
  41. printf("%d\n", node.distance);
  42. return;
  43. }
  44.  
  45. dijkstra_node neighbor;
  46. while (visit_neighbor(graph, node.node, &neighbor.node)) {
  47. neighbor.distance = node.distance + 1;
  48. enq(queue, neighbor);
  49. }
  50. }
  51. printf("impossible\n");
  52. }
  53.  
  54. typedef struct {
  55. int rows;
  56. int cols;
  57. bool *visited;
  58. } chessboard_t;
  59.  
  60. chessboard_t *createBoard(int rows, int cols) {
  61. chessboard_t *b = (chessboard_t *) malloc(sizeof(chessboard_t));
  62. b->rows = rows;
  63. b->cols = cols;
  64. b->visited = (bool*) malloc(sizeof(bool) * rows * cols);
  65. memset(b->visited, 0, sizeof(bool) * rows * cols);
  66. return b;
  67. }
  68.  
  69. int vertices(chessboard_t *b) {
  70. return b->rows * b->cols;
  71. }
  72.  
  73. #define node(b, row, col) ((row) * (b)->cols + (col))
  74.  
  75. bool visit_field(chessboard_t *b, int row, int col, int *neighbor) {
  76. if (row < 0 || row >= b->rows || col < 0 || col >= b->cols) {
  77. return false;
  78. }
  79.  
  80. int node = node(b, row, col);
  81. *neighbor = node;
  82.  
  83. if (b->visited[node]) {
  84. return false;
  85. }
  86. b->visited[node] = true;
  87. return true;
  88. }
  89.  
  90. bool visit_neighbor(chessboard_t *b, int node, int *neighbor) {
  91. int row = node / b->cols;
  92. int col = node % b->cols;
  93.  
  94. return
  95. visit_field(b, row-2, col-1, neighbor) ||
  96. visit_field(b, row-2, col+1, neighbor) ||
  97. visit_field(b, row-1, col-2, neighbor) ||
  98. visit_field(b, row-1, col+2, neighbor) ||
  99. visit_field(b, row+1, col-2, neighbor) ||
  100. visit_field(b, row+1, col+2, neighbor) ||
  101. visit_field(b, row+2, col-1, neighbor) ||
  102. visit_field(b, row+2, col+1, neighbor);
  103. }
  104.  
  105. int main(void) {
  106. int R, C, Gr, Gc, Lr, Lc;
  107.  
  108. while (scanf(" %d %d %d %d %d %d", &R, &C, &Gr, &Gc, &Lr, &Lc) == 6) {
  109. chessboard_t *b = createBoard(R, C);
  110. int ghopper = node(b, Gr-1, Gc-1);
  111. int clover = node(b, Lr-1, Lc-1);
  112. b->visited[ghopper] = true;
  113.  
  114. dijkstra(b, ghopper, clover);
  115. }
  116.  
  117. return 0;
  118. }
  119.