結果

問題 No.402 最も海から遠い場所
ユーザー bal4ubal4u
提出日時 2019-07-19 11:42:58
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 502 ms / 3,000 ms
コード長 1,568 bytes
コンパイル時間 1,078 ms
コンパイル使用メモリ 31,744 KB
実行使用メモリ 107,392 KB
最終ジャッジ日時 2024-12-26 00:02:50
合計ジャッジ時間 3,934 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます
コンパイルメッセージ
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.402 最も海から遠い場所
// 2019.7.19 bal4u

#include <stdio.h>
#include <string.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); while ((c = gc()) >= '0');
	return n;
}

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

#define INF 0x33333333
#define QMAX 20000000
int H, W;
int a[3006][3006];
int q[QMAX+5][2], top, end;
int mv[8][2] = {{-1,-1},{-1,0},{-1,1},{0,1},{0,-1},{1,-1},{1,0},{1,1}};
char map[3006];

void bfs() {
	int i, r, c, v;
	
	while (top != end) {
		int e = end;
		while (top != e) {
			r = q[top][0], c = q[top++][1], v = a[r][c]+1;
//			printf("(%d,%d) v=%d, e=%d, end=%d\n", r, c, v, e, end);
			for (i = 0; i < 8; i++) {
				int rr = r + mv[i][0], cc = c + mv[i][1];
				if (a[rr][cc] > v) {
					a[rr][cc] = v, q[end][0] = rr, q[end++][1] = cc;
				}
			}
		}
	}
}
	
int main()
{
	int r, c, ans;

	H = in()+1, W = in()+1;
	for (c = 2; c <= W; c++) {
		q[end][0] =   1, q[end++][1] = c;
		q[end][0] = H+1, q[end++][1] = c;
	}
	for (r = 2; r <= H; r++) {
		memset(&a[r][2], INF, sizeof(int)*(W-1));
		q[end][0] = r, q[end++][1] = 1;
		q[end][0] = r, q[end++][1] = W+1;
		ins(map+2);
		for (c = 2; c <= W; c++) if (map[c] == '.') {
			a[r][c] = 0, q[end][0] = r, q[end++][1] = c;
		}
	}
	bfs();
	ans = 0; for (r = 2; r <= H; r++) for (c = 2; c <= W; c++) {
		if (a[r][c] > ans) ans = a[r][c];
	}
	printf("%d\n", ans);
	return 0;
}
0