結果
問題 | No.402 最も海から遠い場所 |
ユーザー |
![]() |
提出日時 | 2018-11-05 22:24:56 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 942 ms / 3,000 ms |
コード長 | 1,583 bytes |
コンパイル時間 | 2,455 ms |
コンパイル使用メモリ | 204,124 KB |
最終ジャッジ日時 | 2025-01-06 15:36:31 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include <bits/stdc++.h>using namespace std;using i64 = int64_t;using vi = vector<i64>;using vvi = vector<vi>;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int h, w;cin >> h >> w;vvi b(h + 2, vi(w + 2));for (int i = 1; i < h + 1; i++) {for (int j = 1; j < w + 1; j++) {b[i][j] = 1e9;}}using ii = pair<int, int>;queue<ii> que;for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {char c;cin >> c;if (c == '.') {b[i + 1][j + 1] = 0;}}}for (int i = 0; i < h + 2; i++) {for (int j = 0; j < w + 2; j++) {if (b[i][j] == 0) {que.push(ii(i, j));}}}int dx[] = {1, 1, 1, 0, -1, -1, -1, 0};int dy[] = {1, 0, -1, -1, -1, 0, 1, 1};auto ok = [&](int x, int y) {return 0 <= x && x < h + 2 && 0 <= y && y < w + 2;};while (que.size()) {ii t = que.front();que.pop();for (int i = 0; i < 8; i++) {int x = t.first + dx[i];int y = t.second + dy[i];if (ok(x, y) && b[t.first][t.second] + 1 < b[x][y]) {b[x][y] = b[t.first][t.second] + 1;que.push(ii(x, y));}}}i64 nax = -1;for (int i = 0; i < h + 2; i++) {for (int j = 0; j < w + 2; j++) {nax = max(nax, b[i][j]);}}cout << nax << endl;}