fork download
copy 
  1.  
  2. #include <assert.h>
  3. #include <stdbool.h>
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6.  
  7. typedef struct Vertex {
  8.   size_t x;
  9.   size_t y;
  10. } Vertex;
  11.  
  12. typedef struct Maze {
  13.   size_t width;
  14.   size_t height;
  15.  
  16.   char const *maze;
  17.  
  18.   Vertex start;
  19.   Vertex end;
  20. } Maze;
  21.  
  22. char get_char(Maze const *m, size_t x, size_t y) { return m->maze[x + y * (m->width)]; }
  23.  
  24. bool is_digit(char c) { return '0' <= c && c <= '9'; }
  25.  
  26. Vertex find_destination(Maze const *m, size_t x, size_t y) {
  27.   assert(is_digit(get_char(m, x, y)));
  28.   for (size_t i = 0; i < m->width; ++i) {
  29.     for (size_t j = 0; j < m->height; ++j) {
  30.       if (get_char(m, i, j) == get_char(m, x, y)) {
  31. 	if (i == x && j == y)
  32. 	  continue;
  33. 	else
  34. 	  return (Vertex){ i, j };
  35.       }
  36.     }
  37.   }
  38.   assert(false);
  39. }
  40.  
  41. Maze construct_maze(size_t width, size_t height, char const *maze) {
  42.   Maze m = { width, height, maze, { 0 }, { 0 } };
  43.   bool found_start = false;
  44.   bool found_end = false;
  45.   for (size_t i = 0; i < width; ++i) {
  46.     for (size_t j = 0; j < height; ++j) {
  47.       if (maze[i + j * width] == 'S') {
  48. 	found_start = true;
  49. 	m.start = (Vertex){ i, j };
  50. 	if (found_end) goto done;
  51.       } else if (maze[i + j * width] == 'G') {
  52. 	found_end = true;
  53. 	m.end = (Vertex){ i, j };
  54. 	if (found_start) goto done;
  55.       }
  56.     }
  57.   }
  58.  done:
  59.   return m;
  60. }
  61.  
  62. typedef struct VertexLengthPair {
  63.   Vertex vertex;
  64.   size_t length;
  65. } VertexLengthPair;
  66.  
  67. size_t list_adjacents(Maze const *m, Vertex const *v, Vertex *buffer) {
  68.   size_t len = 0;
  69.   if (v->x != 0) {
  70.     char c = get_char(m, v->x - 1, v->y);
  71.     if (is_digit(c)) {
  72.       buffer[len++] = find_destination(m, v->x - 1, v->y);
  73.     } else if(c != '#') {
  74.       buffer[len++] = (Vertex){ v->x - 1, v->y };
  75.     }
  76.   }
  77.   if (v->x != m->width - 1) {
  78.     char c = get_char(m, v->x + 1, v->y);
  79.     if (is_digit(c)) {
  80.       buffer[len++] = find_destination(m, v->x + 1, v->y);
  81.     } else if(c != '#') {
  82.       buffer[len++] = (Vertex){ v->x + 1, v->y };
  83.     }
  84.   }
  85.   if (v->y != 0) {
  86.     char c = get_char(m, v->x, v->y - 1);
  87.     if (is_digit(c)) {
  88.       buffer[len++] = find_destination(m, v->x, v->y - 1);
  89.     } else if(c != '#') {
  90.       buffer[len++] = (Vertex){ v->x, v->y - 1 };
  91.     }
  92.   }
  93.   if (v->y != m->height - 1) {
  94.     char c = get_char(m, v->x, v->y + 1);
  95.     if (is_digit(c)) {
  96.       buffer[len++] = find_destination(m, v->x, v->y + 1);
  97.     } else if(c != '#') {
  98.       buffer[len++] = (Vertex){ v->x, v->y + 1 };
  99.     }
  100.   }
  101.   return len;
  102. }
  103.  
  104. bool equal_vertex(Vertex const *v, Vertex const *w) { return v->x == w->x && v->y == w->y; }
  105.  
  106. size_t find_shortest_path_length(Maze const *m) {
  107.   bool visited[m->width][m->height];
  108.   for (size_t i = 0; i < m->width; ++i)
  109.     for (size_t j = 0; j < m->height; ++j)
  110.       visited[i][j] = false;
  111.   VertexLengthPair queue[m->width * m->height];
  112.   VertexLengthPair *queue_front = queue;
  113.   VertexLengthPair *queue_last = queue + 1;
  114.   queue_front->vertex = m->start;
  115.   queue_front->length = 0;
  116.   visited[queue_front->vertex.x][queue_front->vertex.y] = true;
  117.  
  118.   while (queue_front != queue_last) {
  119.     Vertex const v = queue_front->vertex;
  120.     size_t const next_length = queue_front->length + 1;
  121.     ++queue_front;
  122.  
  123.     Vertex buf[5];    
  124.     size_t max = list_adjacents(m, &v, buf);
  125.     for (size_t i = 0; i < max; ++i) {
  126.       Vertex *w = buf + i;
  127.       if (visited[w->x][w->y])
  128. 	continue;
  129.       if (equal_vertex(w, &(m->end)))
  130. 	return next_length;
  131.  
  132.       visited[w->x][w->y] = true;
  133.       queue_last->vertex = *w;
  134.       queue_last->length = next_length;
  135.       ++queue_last;
  136.     }
  137.   }
  138.   return 0;
  139. }
  140.  
  141. int main(void) {
  142.   size_t w, h;
  143.   scanf("%zu %zu%*c", &h, &w);
  144.  
  145.   char maze[w * h];
  146.   for (size_t i = 0; i < h; ++i) {
  147.     scanf("%[^\n]%*c", maze + i * w);
  148.   }
  149.  
  150.   Maze m = construct_maze(w, h, maze);
  151.  
  152.   size_t len = find_shortest_path_length(&m);
  153.   if (len)
  154.     printf("%zu\n", len);
  155.   else
  156.     puts("impossible");
  157.  
  158.   return 0;
  159. }
  160.  
Success #stdin #stdout 0s 4264KB
comments (?)
stdin
copy 
4 6
1#S...
....#.
#####.
1..G..
stdout
copy 
7
https://ideone.com/IsSgky
language:
C (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!