結果
問題 | No.402 最も海から遠い場所 |
ユーザー |
![]() |
提出日時 | 2016-07-22 22:32:22 |
言語 | C++14 (gcc 8.3.0) |
結果 |
AC
|
実行時間 | 404 ms |
コード長 | 1,575 Byte |
コンパイル時間 | 1,126 ms |
使用メモリ | 84,092 KB |
最終ジャッジ日時 | 2019-11-26 10:48:45 |
テストケース
テストケース表示入力 | 結果 | 実行時間 使用メモリ |
---|---|---|
00sample_01.txt | AC | 3 ms
1,548 KB |
00sample_02.txt | AC | 3 ms
1,548 KB |
00sample_03.txt | AC | 4 ms
1,596 KB |
01input_01.txt | AC | 3 ms
1,532 KB |
01input_02.txt | AC | 2 ms
1,552 KB |
01input_03.txt | AC | 3 ms
1,552 KB |
01input_04.txt | AC | 3 ms
1,544 KB |
01input_05.txt | AC | 3 ms
1,528 KB |
01input_06.txt | AC | 3 ms
1,548 KB |
02random_01.txt | AC | 3 ms
1,544 KB |
02random_02.txt | AC | 3 ms
1,548 KB |
02random_03.txt | AC | 3 ms
1,584 KB |
02random_04.txt | AC | 3 ms
1,572 KB |
02random_05.txt | AC | 6 ms
1,928 KB |
02random_06.txt | AC | 4 ms
1,736 KB |
02random_07.txt | AC | 15 ms
3,660 KB |
02random_08.txt | AC | 21 ms
4,740 KB |
02random_09.txt | AC | 211 ms
41,164 KB |
02random_10.txt | AC | 404 ms
18,576 KB |
03max_01.txt | AC | 325 ms
84,016 KB |
03max_02.txt | AC | 308 ms
10,684 KB |
03max_03.txt | AC | 337 ms
84,092 KB |
ソースコード
#define _USE_MATH_DEFINES #include <algorithm> #include <cstdio> #include <functional> #include <iostream> #include <cfloat> #include <climits> #include <cstdlib> #include <cstring> #include <cmath> #include <map> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <time.h> #include <unordered_set> #include <vector> #include <random> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> i_i; typedef pair<ll, int> ll_i; typedef pair<double, int> d_i; typedef pair<ll, ll> ll_ll; typedef pair<double, double> d_d; struct edge { int u, v; ll w; }; int INF = INT_MAX / 2; ll MOD = 1000000007; ll _MOD = 1000000009; double EPS = 1e-10; char c[3010]; int main() { int H, W; cin >> H >> W; vector<string> a(H); for (int y = 0; y < H; y++) { scanf("%s", c); a[y] = c; } queue<i_i> q; for (int y = 0; y < H; y++) for (int x = 0; x < W; x++) if (a[y][x] == '.') q.push(i_i(y, x)); for (int y = 0; y < H; y++) { q.push(i_i(y, -1)); q.push(i_i(y, W)); } for (int x = 0; x < W; x++) { q.push(i_i(-1, x)); q.push(i_i(H, x)); } int t; for (t = 0; !q.empty(); t++) { queue<i_i> _q; while (!q.empty()) { i_i yx = q.front(); q.pop(); int y = yx.first, x = yx.second; for (int dy = -1; dy <= 1; dy++) for (int dx = -1; dx <= 1; dx++) { int _y = y + dy, _x = x + dx; if (0 <= _y && _y < H && 0 <= _x && _x < W && a[_y][_x] == '#') { a[_y][_x] = '.'; _q.push(i_i(_y, _x)); } } } q = _q; } cout << t - 1 << endl; }