結果

問題 No.402 最も海から遠い場所
ユーザー femto
提出日時 2016-07-22 23:06:39
言語 C++11
(gcc 4.8.5)
結果
AC  
実行時間 776 ms
コード長 1,073 Byte
コンパイル時間 570 ms
使用メモリ 119,380 KB
最終ジャッジ日時 2019-11-26 10:55:01

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
00sample_01.txt AC 32 ms
36,928 KB
00sample_02.txt AC 31 ms
36,928 KB
00sample_03.txt AC 32 ms
37,140 KB
01input_01.txt AC 31 ms
36,908 KB
01input_02.txt AC 32 ms
36,924 KB
01input_03.txt AC 32 ms
36,932 KB
01input_04.txt AC 32 ms
36,908 KB
01input_05.txt AC 32 ms
36,936 KB
01input_06.txt AC 32 ms
36,916 KB
02random_01.txt AC 31 ms
36,936 KB
02random_02.txt AC 32 ms
36,936 KB
02random_03.txt AC 32 ms
37,040 KB
02random_04.txt AC 31 ms
36,980 KB
02random_05.txt AC 35 ms
37,516 KB
02random_06.txt AC 33 ms
37,700 KB
02random_07.txt AC 46 ms
39,316 KB
02random_08.txt AC 52 ms
39,864 KB
02random_09.txt AC 268 ms
60,360 KB
02random_10.txt AC 776 ms
49,608 KB
03max_01.txt AC 418 ms
119,380 KB
03max_02.txt AC 452 ms
45,876 KB
03max_03.txt AC 384 ms
82,868 KB
テストケース一括ダウンロード

ソースコード

diff #
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <iomanip>
#include <queue>
using namespace std;

const int INF = 1000000;
char b[3010][3010];
int d[3010][3010];
int dx[8] = { 0, 1, 1, 1, 0, -1, -1, -1 }, dy[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };

struct P {
	int x, y;
};

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int H, W;
	cin >> H >> W;

	fill((int*)begin(d), (int*)end(d), INF);

	queue<P> q;
	for(int i = 0; i < H + 2; i++) {
		for(int j = 0; j < W + 2; j++) {
			if(i != 0 && i != H + 1 && j != 0 && j != W + 1) {
				cin >> b[i][j];
			}
			else {
				b[i][j] = '.';
			}
			if(b[i][j] == '.') {
				d[i][j] = 0;
				q.push(P{ j, i });
			}
		}
	}

	int ans = 0;
	while(!q.empty()) {
		P p = q.front();
		q.pop();

		for(int i = 0; i < 8; i++) {
			int ny = p.y + dy[i], nx = p.x + dx[i];
			if(1 <= nx && nx <= W && 1 <= ny && ny <= H && d[p.y][p.x] + 1 < d[ny][nx]) {
				d[ny][nx] = d[p.y][p.x] + 1;
				q.push(P{ nx, ny });
				ans = max(ans, d[ny][nx]);
			}
		}
	}

	cout << ans << endl;
}
0