結果

問題 No.402 最も海から遠い場所
ユーザー kyuna
提出日時 2019-08-31 21:44:04
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 752 ms / 3,000 ms
コード長 1,463 bytes
コンパイル時間 788 ms
コンパイル使用メモリ 89,300 KB
実行使用メモリ 123,504 KB
最終ジャッジ日時 2024-11-25 08:43:56
合計ジャッジ時間 5,402 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

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