21b.c (2306B)
1 /* 2 This is another problem I did not enjoy. Once again, it was only solvable 3 because of the carefully crafted input case. This makes the problem 4 solvable, but at the same time it leaves you wondering - which unsaid 5 assumptions are true and which are not? 6 7 For example, in my first 14 attempts or so I assumed that every non-# cell 8 was reached at the same time as if there were no #-cells. A reasonable 9 assumption, and almost true. Unfortunately there were some cells that 10 were completely enclosed by #-cells, and thus unreachable. See fuckyou.png 11 and fuckyou2.png. 12 */ 13 14 #include <inttypes.h> 15 #include <stdbool.h> 16 #include <stdio.h> 17 #include <string.h> 18 19 #define N 200 20 #define S 202300L 21 22 char map[N][N]; 23 int64_t n; 24 25 int go(char m[][N], int i, int j) { 26 if (i >= 0 && j >= 0 && i < n && j < n && m[i][j] == '.') { 27 m[i][j] = 'S'; 28 return 1; 29 } 30 return 0; 31 } 32 33 int64_t flood(int64_t x, int64_t y, int64_t steps) { 34 int64_t c, i, j; 35 char tmp[N][N]; 36 for (int i = 0; i < n; i++) memcpy(tmp[i], map[i], n*sizeof(char)); 37 tmp[x][y] = 'S'; 38 for (int s = 0; s < steps; s++) { 39 for (i = 0, c = 0; i < n; i++) { 40 for (j = (s+x+y+i)%2; j < n; j += 2) { 41 if (tmp[i][j] == 'S') { 42 tmp[i][j] = '.'; 43 c += go(tmp, i-1, j) + 44 go(tmp, i+1, j) + 45 go(tmp, i, j-1) + 46 go(tmp, i, j+1); 47 } 48 } 49 } 50 } 51 return c; 52 } 53 54 int main() { 55 for (n = 0; fgets(map[n], N, stdin) != NULL; n++) ; 56 map[n/2][n/2] = '.'; 57 58 int64_t fulleven = flood(n/2, n/2, n-1); 59 int64_t fullodd = flood(n/2, n/2, n); 60 int64_t arrowr = flood(n/2, 0, n-1); 61 int64_t arrowl = flood(n/2, n-1, n-1); 62 int64_t arrowd = flood(0, n/2, n-1); 63 int64_t arrowu = flood(n-1, n/2, n-1); 64 int64_t topl = flood(0, 0, n/2-1); 65 int64_t topr = flood(0, n-1, n/2-1); 66 int64_t botl = flood(n-1, 0, n/2-1); 67 int64_t botr = flood(n-1, n-1, n/2-1); 68 int64_t cutbr = flood(0, 0, n/2+n-1); 69 int64_t cutbl = flood(0, n-1, n/2+n-1); 70 int64_t cuttr = flood(n-1, 0, n/2+n-1); 71 int64_t cuttl = flood(n-1, n-1, n/2+n-1); 72 73 int64_t fulls = S*S*fulleven + (S-1)*(S-1)*fullodd; 74 int64_t smallborder = S*(topl + topr + botl + botr); 75 int64_t bigborder = (S-1)*(cutbr + cutbl + cuttr + cuttl); 76 int64_t arrows = arrowr + arrowl + arrowu + arrowd; 77 int64_t final = fulls + smallborder + bigborder + arrows; 78 79 printf("%" PRId64 "\n", final); 80 81 return 0; 82 }