結果
問題 | No.402 最も海から遠い場所 |
ユーザー |
|
提出日時 | 2023-12-08 02:25:57 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 647 ms / 3,000 ms |
コード長 | 1,385 bytes |
コンパイル時間 | 3,367 ms |
コンパイル使用メモリ | 260,604 KB |
実行使用メモリ | 259,360 KB |
最終ジャッジ日時 | 2024-09-27 02:36:22 |
合計ジャッジ時間 | 8,245 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#include <bits/stdc++.h>using namespace std;constexpr int DX[8] = {0, 0, 1, -1, 1, 1, -1, -1}, DY[8] = {1, -1, 0, 0, 1, -1, 1, -1};int main() {ios::sync_with_stdio(false);cin.tie(0);int H, W;cin >> H >> W;vector<vector<int>> d(H + 2, vector<int>(W + 2, 0));for(int i = 1; i <= H; i++) {for(int j = 1; j <= W; j++) {char c;cin >> c;if(c == '#') { d[i][j] = 1e9; }}}queue<tuple<int, int, int>> q;for(int i = 0; i < H + 2; i++) {for(int j = 0; j < W + 2; j++) {if(!d[i][j]) {for(int k = 0; k < 8; k++) {int ni = i + DX[k], nj = j + DY[k];if(ni < 0 || ni >= H + 2 || nj < 0 || nj >= W + 2) { continue; }if(!d[ni][nj]) { continue; }q.emplace(i, j, k);}}}}while(!q.empty()) {auto [i, j, k] = q.front();q.pop();int ni = i + DX[k], nj = j + DY[k];if(ni < 0 || ni >= H + 2 || nj < 0 || nj >= W + 2) { continue; }if(d[ni][nj] > d[i][j] + 1) {d[ni][nj] = d[i][j] + 1;q.emplace(ni, nj, k);if(k == 4 || k == 6) { q.emplace(ni, nj, 0); }if(k == 5 || k == 7) { q.emplace(ni, nj, 1); }if(k == 4 || k == 5) { q.emplace(ni, nj, 2); }if(k == 6 || k == 7) { q.emplace(ni, nj, 3); }}}int r = 0;for(auto &i : d) { r = max(r, ranges::max(i)); }cout << r << "\n";}