結果
問題 |
No.402 最も海から遠い場所
|
ユーザー |
|
提出日時 | 2023-08-14 15:52:00 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 692 ms / 3,000 ms |
コード長 | 1,361 bytes |
コンパイル時間 | 6,522 ms |
コンパイル使用メモリ | 126,464 KB |
実行使用メモリ | 129,992 KB |
最終ジャッジ日時 | 2024-11-22 14:20:34 |
合計ジャッジ時間 | 11,395 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include <iostream> #include <vector> #include <deque> using namespace std; int main() { int H, W; cin >> H >> W; vector<string> lsHW(H + 2, string(W + 2, '.')); for (int i = 1; i <= H; ++i) { string row; cin >> row; lsHW[i] = '.' + row + '.'; } H += 2; W += 2; const int INF = 5000; vector<vector<int>> cost(H, vector<int>(W, INF)); vector<pair<int, int>> dxy = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}, {1, 1}, {-1, 1}, {1, -1}, {-1, -1}}; deque<pair<int, int>> d; for (int i = 0; i < H; ++i) { for (int j = 0; j < W; ++j) { if (lsHW[i][j] == '.') { cost[i][j] = 0; d.emplace_back(i, j); } } } int cmax = 0; while (!d.empty()) { int x = d.front().first; int y = d.front().second; d.pop_front(); for (const auto& dxdy : dxy) { int dx = dxdy.first; int dy = dxdy.second; if (0 <= x + dx && x + dx < H && 0 <= y + dy && y + dy < W) { if (cost[x + dx][y + dy] > cost[x][y] + 1) { cost[x + dx][y + dy] = cost[x][y] + 1; cmax = cost[x][y] + 1; d.emplace_back(x + dx, y + dy); } } } } cout << cmax << endl; return 0; }