結果

問題 No.402 最も海から遠い場所
ユーザー bal4ubal4u
提出日時 2019-07-19 11:42:58
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 281 ms / 3,000 ms
コード長 1,568 bytes
コンパイル時間 744 ms
コンパイル使用メモリ 30,360 KB
実行使用メモリ 109,368 KB
最終ジャッジ日時 2023-08-26 21:15:23
合計ジャッジ時間 2,795 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,384 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 1 ms
4,376 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 1 ms
4,376 KB
testcase_11 AC 1 ms
4,384 KB
testcase_12 AC 1 ms
4,376 KB
testcase_13 AC 2 ms
6,180 KB
testcase_14 AC 2 ms
5,960 KB
testcase_15 AC 10 ms
11,732 KB
testcase_16 AC 11 ms
14,052 KB
testcase_17 AC 140 ms
61,172 KB
testcase_18 AC 281 ms
109,356 KB
testcase_19 AC 189 ms
109,356 KB
testcase_20 AC 221 ms
109,304 KB
testcase_21 AC 187 ms
109,368 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: 関数 ‘in’ 内:
main.c:8:14: 警告: 関数 ‘getchar_unlocked’ の暗黙的な宣言です [-Wimplicit-function-declaration]
    8 | #define gc() getchar_unlocked()
      |              ^~~~~~~~~~~~~~~~
main.c:14:24: 備考: 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