結果
問題 | No.402 最も海から遠い場所 |
ユーザー | wing3196 |
提出日時 | 2016-07-22 22:45:06 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 1,070 ms / 3,000 ms |
コード長 | 1,058 bytes |
コンパイル時間 | 2,313 ms |
コンパイル使用メモリ | 150,036 KB |
実行使用メモリ | 242,136 KB |
最終ジャッジ日時 | 2023-08-06 09:51:12 |
合計ジャッジ時間 | 7,975 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
12,968 KB |
testcase_01 | AC | 5 ms
12,888 KB |
testcase_02 | AC | 5 ms
13,156 KB |
testcase_03 | AC | 4 ms
12,896 KB |
testcase_04 | AC | 5 ms
12,872 KB |
testcase_05 | AC | 4 ms
12,884 KB |
testcase_06 | AC | 4 ms
12,960 KB |
testcase_07 | AC | 4 ms
12,916 KB |
testcase_08 | AC | 4 ms
12,924 KB |
testcase_09 | AC | 5 ms
13,064 KB |
testcase_10 | AC | 5 ms
13,080 KB |
testcase_11 | AC | 5 ms
13,148 KB |
testcase_12 | AC | 5 ms
12,924 KB |
testcase_13 | AC | 10 ms
14,056 KB |
testcase_14 | AC | 7 ms
13,800 KB |
testcase_15 | AC | 34 ms
19,764 KB |
testcase_16 | AC | 39 ms
19,072 KB |
testcase_17 | AC | 512 ms
119,936 KB |
testcase_18 | AC | 760 ms
33,136 KB |
testcase_19 | AC | 1,070 ms
242,136 KB |
testcase_20 | AC | 681 ms
21,668 KB |
testcase_21 | AC | 949 ms
241,532 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define int long long const int INF = LLONG_MAX/2; const int dx[] = {1, 1, 1, 0, -1, -1, -1, 0}, dy[] = {-1, 0, 1, 1, 1, 0, -1, -1}; int H, W; char fld[3002][3002]; bool isUsed[3002][3002]; signed main() { fill(fld[0], fld[0] + 3002*3002, '.'); cin >> H >> W; queue< pair< pair<int, int>, int> > q; for (int i = 1; i < H + 1; i++) { for (int j = 1; j < W + 1; j++) { cin >> fld[i][j]; } } for (int i = 0; i < H + 2; i++) { for (int j = 0; j < W + 2; j++) { if (fld[i][j] == '.') q.emplace(make_pair(make_pair(j, i), 0)); } } int ma = 0; while (!q.empty()) { pair<int, int> p = q.front().first; int cost = q.front().second; q.pop(); isUsed[p.second][p.first] = true; ma = cost; for (int i = 0; i < 8; i++) { int nx = p.first + dx[i], ny = p.second + dy[i]; if (nx < 0 || W + 2 <= nx || ny < 0 || H + 2 <= ny || isUsed[ny][nx]) continue; isUsed[ny][nx] = true; q.emplace(make_pair(make_pair(nx, ny), cost + 1)); } } printf("%lld\n", ma); return 0; }