Submission #69932987

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <stdlib.h>
int H, W;
char** S;
struct yx_s {
  int y, x;
};
struct yx_s listbuf[2][312345];
int main(void) {
  char buf[128];
  int i, j;
  int cnt = 0, next_cnt = 0;
  struct yx_s* list = listbuf[0], *next_list = listbuf[1], *temp;
  int ans = 0;
  if (fgets(buf, sizeof(buf), stdin) == NULL || sscanf(buf, "%d%d", &H, &W) != 2) return 1;
  S = malloc(sizeof(*S) * H);
  if (S == NULL) return 2;
  S[0] = malloc(sizeof(**S) * (W + 8) * H);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <stdlib.h>

int H, W;
char** S;

struct yx_s {
	int y, x;
};
struct yx_s listbuf[2][312345];

int main(void) {
	char buf[128];
	int i, j;
	int cnt = 0, next_cnt = 0;
	struct yx_s* list = listbuf[0], *next_list = listbuf[1], *temp;
	int ans = 0;
	if (fgets(buf, sizeof(buf), stdin) == NULL || sscanf(buf, "%d%d", &H, &W) != 2) return 1;
	S = malloc(sizeof(*S) * H);
	if (S == NULL) return 2;
	S[0] = malloc(sizeof(**S) * (W + 8) * H);
	if (S[0] == NULL) return 2;
	for (i = 0; i < H; i++) {
		S[i] = S[0] + (size_t)(W + 8) * i;
		if (fgets(S[i], W + 8, stdin) == NULL) return 1;
	}
	for (i = 0; i < H; i++) {
		for (j = 0; j < W; j++) {
			if (S[i][j] == '#') {
				list[cnt++] = (struct yx_s){ i, j };
			}
		}
	}
	while (cnt > 0) {
		/* 前のイテレーションで増えた黒マスの周辺のみをチェックする */
		for (i = 0; i < cnt; i++) {
			for (j = 0; j < 4; j++) {
				int y = list[i].y + (j < 2) * ((j & 1) * 2 - 1);
				int x = list[i].x + (j >= 2) * ((j & 1) * 2 - 1);
				if (0 <= y && y < H && 0 <= x && x < W && S[y][x] != '#') {
					int k, rcnt = 0;
					for (k = 0; k < 4; k++) {
						/* sample y/x */
						int sy = y + (k < 2) * ((k & 1) * 2 - 1);
						int sx = x + (k >= 2) * ((k & 1) * 2 - 1);
						rcnt += 0 <= sy && sy < H && 0 <= sx && sx < W && S[sy][sx] == '#';
					}
					if (rcnt == 1) {
						next_list[next_cnt++] = (struct yx_s){ y, x };
					}
				}
			}
		}
		for (i = 0; i < next_cnt; i++) {
			S[next_list[i].y][next_list[i].x] = '#';
		}
		cnt = next_cnt;
		temp = list;
		list = next_list;
		next_list = temp;
		next_cnt = 0;
	}
	for (i = 0; i < H; i++) {
		for (j = 0; j < W; j++) {
			ans += S[i][j] == '#';
		}
	}
	printf("%d\n", ans);
	free(S[0]);
	free(S);
	return 0;
}

Submission Info

Judge Result