21a.c (1176B)
1 #include <stdbool.h> 2 #include <stdio.h> 3 #include <string.h> 4 5 #define N 200 6 7 typedef struct { int i, j; } point_t; 8 9 char map[N][N]; 10 int n, nq, nnext; 11 point_t s, q[N*N], nextq[N*N]; 12 13 bool bad(point_t p) { 14 int i = p.i, j = p.j; 15 return i < 0 || j < 0 || i >= n || j >= n || map[i][j] == '#'; 16 } 17 18 void add(point_t p) { 19 if (bad(p)) return; 20 for (int i = 0; i < nnext; i++) 21 if (nextq[i].i == p.i && nextq[i].j == p.j) 22 return; 23 nextq[nnext++] = p; 24 } 25 26 point_t up(point_t p) { return (point_t) {.i = p.i-1, .j = p.j}; } 27 point_t down(point_t p) { return (point_t) {.i = p.i+1, .j = p.j}; } 28 point_t right(point_t p) { return (point_t) {.i = p.i, .j = p.j+1}; } 29 point_t left(point_t p) { return (point_t) {.i = p.i, .j = p.j-1}; } 30 31 int main() { 32 for (n = 0; fgets(map[n], N, stdin) != NULL; n++) 33 for (int i = 0; map[n][i] != '\n'; i++) 34 if (map[n][i] == 'S') 35 s = (point_t) {.i = n, .j = i}; 36 37 int d = 64; 38 add(s); 39 for (int i = 0; i < d; i++) { 40 memcpy(q, nextq, nnext * sizeof(point_t)); 41 nq = nnext; 42 nnext = 0; 43 for (int j = 0; j < nq; j++) { 44 add(up(q[j])); 45 add(down(q[j])); 46 add(right(q[j])); 47 add(left(q[j])); 48 } 49 } 50 51 printf("%d\n", nnext); 52 return 0; 53 }