結果
問題 | No.402 最も海から遠い場所 |
ユーザー |
|
提出日時 | 2016-07-22 22:34:18 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 687 ms / 3,000 ms |
コード長 | 1,041 bytes |
コンパイル時間 | 2,682 ms |
コンパイル使用メモリ | 172,280 KB |
実行使用メモリ | 121,204 KB |
最終ジャッジ日時 | 2024-11-06 12:42:16 |
合計ジャッジ時間 | 5,912 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { int h, w; cin >> h >> w; vector<string> g(h + 2, string(w + 2, '.')); for (int i = 0; i < h; i++) { string s; cin >> s; for (int j = 0; j < w; j++) { g[i + 1][j + 1] = s[j]; } } h += 2; w += 2; vector<vector<int>> dist(h, vector<int>(w, -1)); queue<pair<int, int>> q; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (g[i][j] != '#') { dist[i][j] = 0; q.emplace(i, j); } } } while (!q.empty()) { int y, x; tie(y, x) = q.front(); q.pop(); const int dy[] = { 0, 0, 1, 1, 1, -1, -1, -1 }; const int dx[] = { 1, -1, 1, 0, -1, 1, 0, -1 }; for (int k = 0; k < 8; k++) { int ny = y + dy[k]; int nx = x + dx[k]; if (ny < 0 || nx < 0 || ny >= h || nx >= w) continue; if (dist[ny][nx] == -1) { dist[ny][nx] = dist[y][x] + 1; q.emplace(ny, nx); } } } int maxi = 0; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { maxi = max(maxi, dist[i][j]); } } cout << maxi << endl; }