結果

問題 No.402 最も海から遠い場所
ユーザー kyunakyuna
提出日時 2019-08-31 21:44:05
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 727 ms / 3,000 ms
コード長 1,463 bytes
コンパイル時間 1,028 ms
コンパイル使用メモリ 89,692 KB
実行使用メモリ 123,572 KB
最終ジャッジ日時 2024-11-25 08:44:07
合計ジャッジ時間 4,895 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 1 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 1 ms
5,248 KB
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 2 ms
5,248 KB
testcase_13 AC 7 ms
5,248 KB
testcase_14 AC 3 ms
5,248 KB
testcase_15 AC 28 ms
5,760 KB
testcase_16 AC 26 ms
6,784 KB
testcase_17 AC 482 ms
45,428 KB
testcase_18 AC 727 ms
54,272 KB
testcase_19 AC 502 ms
123,572 KB
testcase_20 AC 686 ms
50,048 KB
testcase_21 AC 498 ms
87,112 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
const int INF = (int)1e9 + 7;

template<class T> ostream& operator<<(ostream& os, const vector<T>& vec) { for (auto &vi: vec) os << vi << " "; return os; }

int main() {
    int h, w; cin >> h >> w;
    vector<string> field(h);
    for (auto &s: field) cin >> s;
    vector<vector<int>> dist(h, vector<int>(w, INF));
    queue<pair<int, int>> que;
    for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) {
        if (field[i][j] == '.') {
            dist[i][j] = 0; que.emplace(i, j);
        }
    }
    for (int i = 0; i < h; i++) que.emplace(i, -1), que.emplace(i, w);
    for (int j = 0; j < w; j++) que.emplace(-1, j), que.emplace(h, j);
    while (!que.empty()) {
        int i, j; tie(i, j) = que.front(); que.pop();
        for (int di: {-1, 0, 1}) for (int dj: {-1, 0, 1}) {
            int ni = i + di, nj = j + dj;
            if (ni < 0 || ni >= h || nj < 0 || nj >= w) continue;
            if (field[ni][nj] == '#' && dist[ni][nj] == INF) {
                if (i < 0 || i >= h || j < 0 || j >= w) {
                    dist[ni][nj] = 1; que.emplace(ni, nj);
                } else {
                    dist[ni][nj] = dist[i][j] + 1; que.emplace(ni, nj);
                }
            }
        }
    }
    int ma = 0;
    for (auto d: dist) ma = max(ma, *max_element(d.begin(), d.end()));
    cout << ma << endl;
    return 0;
}
0