結果
問題 | No.157 2つの空洞 |
ユーザー |
![]() |
提出日時 | 2020-05-30 23:42:38 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 1,157 bytes |
コンパイル時間 | 1,474 ms |
コンパイル使用メモリ | 168,736 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-08 19:21:03 |
合計ジャッジ時間 | 2,259 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 16 |
ソースコード
#include <bits/stdc++.h> using namespace std; int W, H; string C[30]; const int dx[] = {1, 0, -1, 0}; const int dy[] = {0, -1, 0, 1}; void f(int x, int y) { if (x < 0 || y < 0 || x >= H || y >= W) return; if (C[x][y] == '.') { C[x][y] = '?'; for (int i = 0; i < 4; i++) { f(x + dx[i], y + dy[i]); } } } int main() { cin >> W >> H; for (int i = 0; i < H; i++) { cin >> C[i]; } bool flag = false; for (int x = 0; x < H; x++) { for (int y = 0; y < W; y++) { if (C[x][y] == '.') { flag = true; f(x, y); } if (flag) break; } if (flag) break; } int ans = 100; for (int x1 = 0; x1 < H; x1++) { for (int x2 = 0; x2 < H; x2++) { for (int y1 = 0; y1 < W; y1++) { for (int y2 = 0; y2 < W; y2++) { if (C[x1][y1] == '.' && C[x2][y2] == '?') ans = min(ans, abs(x1 - x2) + abs(y1 - y2) - 1); } } } } cout << ans << endl; }