結果

問題 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0