結果

問題 No.157 2つの空洞
コンテスト
ユーザー bal4u
提出日時 2019-04-21 09:03:46
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 2,423 bytes
コンパイル時間 350 ms
コンパイル使用メモリ 32,768 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-04 21:09:41
合計ジャッジ時間 987 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function 'in':
main.c:8:14: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration]
    8 | #define gc() getchar_unlocked()
      |              ^~~~~~~~~~~~~~~~
main.c:14:24: note: in expansion of macro 'gc'
   14 |         int n = 0, c = gc();
      |                        ^~

ソースコード

diff # 

// yukicoder: No.157 2つの空洞
// 2019.4.21 bal4u

#include <stdio.h>

//// 高速入力
#if 1
#define gc() getchar_unlocked()
#else
#define gc() getchar()
#endif
int in()    // 非負整数の入力
{
	int n = 0, c = gc();
	do n = 10 * n + (c & 0xf), c = gc(); while (c >= '0');
	return n;
}

void ins(char *s)  // 文字列の入力　スペース以下の文字で入力終了
{
	do *s = gc();
	while (*s++ > ' ');
	*(s-1) = 0;
}

/* UNION-FIND library */
#define MAX 500
int id[MAX], size[MAX];
void init(int n) { int i; for (i = 0; i < n; i++) id[i] = i, size[i] = 1; }
int root(int i) { while (i != id[i]) id[i] = id[id[i]], i = id[i]; return i; }
int connected(int p, int q) { return root(p) == root(q); }
void unite(int p, int q)
{
    int i = root(p), j = root(q); if (i == j) return;
    if (size[i] < size[j]) id[i] = j, size[j] += size[i]; else id[j] = i, size[i] += size[j];
}

int H, W;
char map[22][22];
int encode[22][22], sz;

typedef struct { int r, c; } Q;
Q q[500]; int top;
char vis[22][22];
int mv[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};

void dfs(int r0, int c0)
{
	int i, r, c, rr, cc;
	q[0].r = r0, q[0].c = c0, top = 1;
	while (top) {
		r = q[--top].r, c = q[top].c;
		if (vis[r][c]) continue;
		vis[r][c] = 1;
		for (i = 0; i < 4; i++) {
			rr = r + mv[i][0], cc = c + mv[i][1];
			if (rr < 0 || rr >= H || cc < 0 || cc >= W || map[rr][cc] == '#')
				continue;
			unite(encode[r][c], encode[rr][cc]);
			q[top].r = rr, q[top++].c = cc;
		}
	}
}

int getMin(int r, int c)
{
	int i, a, b, max;
	max = 500;
	for (i = 0; i < top; i++) {
		a = r - q[i].r; if (a < 0) a = -a;
		b = c - q[i].c; if (b < 0) b = -b;
		a += b;
		if (a < max) max = a;
	}
	return max;
}

int main()
{
	int r, c, r0, c0, r1, c1, m, max;

	W = in(), H = in();
	init(W*H), sz = 0;
	for (r = 0; r < H; r++) {
		ins(map[r]);
		for (c = 0; c < W; c++) encode[r][c] = sz++;
	}
	r0 = -1;
	for (r = 0; r < H; r++) for (c = 0; c < W; c++) {
		if (map[r][c] == '.') {
			if (r0 < 0) r0 = r, c0 = c;
			dfs(r, c);
		}
	}
	top = 0, r1 = -1;
	for (r = r0; r < H; r++) for (c = 0; c < W; c++) {
		if (root(encode[r][c]) == root(encode[r0][c0]))
			q[top].r = r, q[top++].c = c;
		else if (r1 < 0 && map[r][c] == '.') r1 = r, c1 = c;
	}
	max = 500;
	for (r = r1; r < H; r++) for (c = 0; c < W; c++) {
		if (root(encode[r1][c1]) == root(encode[r][c])) {
			if ((m = getMin(r, c)) < max) max = m;
		}
	}
	printf("%d\n", max-1);
	return 0;
}
0