結果
問題 | No.402 最も海から遠い場所 |
ユーザー |
|
提出日時 | 2020-11-21 00:31:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 412 ms / 3,000 ms |
コード長 | 1,640 bytes |
コンパイル時間 | 1,170 ms |
コンパイル使用メモリ | 86,016 KB |
最終ジャッジ日時 | 2025-01-16 03:40:08 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
ソースコード
#line 2 "/Users/tiramister/CompetitiveProgramming/Cpp/CppLibrary/Tools/vector_alias.hpp"#include <vector>template <class T>std::vector<T> vec(int len, T elem) { return std::vector<T>(len, elem); }#line 2 "main.cpp"#include <iostream>#line 5 "main.cpp"#include <string>#include <queue>#include <tuple>void solve() {int h, w;std::cin >> h >> w;std::vector<std::string> ss(h);for (auto &s : ss) std::cin >> s;auto dist = vec(h, vec(w, -1));std::queue<std::tuple<int, int, int>> que;for (int x = -1; x <= h; ++x) {for (int y = -1; y <= w; ++y) {if (x < 0 || h <= x ||y < 0 || w <= y) {que.emplace(0, x, y);} else if (ss[x][y] == '.') {dist[x][y] = 0;que.emplace(0, x, y);}}}while (!que.empty()) {auto [d, x, y] = que.front();que.pop();for (int dx = -1; dx <= 1; ++dx) {for (int dy = -1; dy <= 1; ++dy) {int nx = x + dx,ny = y + dy;if (nx < 0 || h <= nx ||ny < 0 || w <= ny ||dist[nx][ny] != -1) continue;dist[nx][ny] = d + 1;que.emplace(dist[nx][ny], nx, ny);}}}int ans = 0;for (int x = 0; x < h; ++x) {for (int y = 0; y < w; ++y) {ans = std::max(ans, dist[x][y]);}}std::cout << ans << "\n";}int main() {std::cin.tie(nullptr);std::ios::sync_with_stdio(false);solve();return 0;}