結果
問題 | No.157 2つの空洞 |
ユーザー |
![]() |
提出日時 | 2015-03-13 02:00:10 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 91 ms / 2,000 ms |
コード長 | 1,795 bytes |
コンパイル時間 | 686 ms |
コンパイル使用メモリ | 88,604 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-28 22:47:13 |
合計ジャッジ時間 | 2,001 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 16 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <string> #include <sstream> #include <cstring> #include <cstdio> #include <cstdlib> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <numeric> #include <cctype> #include <tuple> #include <array> #include <climits> #include <bitset> #include <cassert> #include <unordered_map> #ifdef _MSC_VER #include <agents.h> #endif #define FOR(i, a, b) for(int i = (a); i < (int)(b); ++i) #define rep(i, n) FOR(i, 0, n) #define ALL(v) v.begin(), v.end() #define REV(v) v.rbegin(), v.rend() #define MEMSET(v, s) memset(v, s, sizeof(v)) #define UNIQUE(v) (v).erase(unique(ALL(v)), (v).end()) #define MP make_pair #define MT make_tuple using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> P; const int N = 404; int dist[N][N]; int w, h; int f(int i, int j){ return i*w + j; } P g(int x){ return MP(x / w, x % w); } int dx[] = {0, 1, 0, -1}; int dy[] = {-1, 0, 1, 0}; int main(){ cin.tie(0); ios::sync_with_stdio(false); cout.setf(ios::fixed); cout.precision(20); cin >> w >> h; vector<string> a(h); rep(i, h) cin >> a[i]; int n = w*h; rep(i, n) rep(j, n) dist[i][j] = i == j ? 0 : 1e9; rep(i, h) rep(j, w){ rep(d, 4){ int ni = i + dy[d], nj = j + dx[d]; if (ni < 0 || ni >= h || nj < 0 || nj >= w) continue; int c = a[i][j] == '#' || a[ni][nj] == '#'; int x = f(i, j), y = f(ni, nj); dist[x][y] = dist[y][x] = c; } } rep(i, n) rep(j, n) rep(k, n) dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]); int ans = 1e9; rep(i, h) rep(j, w) rep(k, h) rep(l, w){ if (a[i][j] == '#' || a[k][l] == '#') continue; int x = f(i, j), y = f(k, l); if (dist[x][y]) ans = min(ans, dist[x][y] - 1); } cout << ans << endl; }