結果
問題 | No.157 2つの空洞 |
ユーザー |
![]() |
提出日時 | 2014-12-03 23:32:18 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2 ms / 2,000 ms |
コード長 | 2,165 bytes |
コンパイル時間 | 668 ms |
コンパイル使用メモリ | 91,776 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-11 14:42:40 |
合計ジャッジ時間 | 1,426 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 16 |
ソースコード
#include <algorithm> #include <cfloat> #include <climits> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <functional> #include <iostream> #include <map> #include <memory> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; #define sz size() #define pb push_back #define mp make_pair #define fi first #define se second #define all(c) (c).begin(), (c).end() #define rep(i,a,b) for(int i=(a);i<(b);++i) #define clr(a, b) memset((a), (b) ,sizeof(a)) #define MOD 1000000009 int w,h; int d[22][22]; vector<string> v; void f(int y, int x, int index){ static int dx[4]={-1,0,0,1}; static int dy[4]={0,-1,1,0}; if(y == -1 || x == -1 || y == h || x == w)return; if(v[y][x]=='#'||d[y][x]!=-1)return; d[y][x] = index; rep(i,0,4)f(y+dy[i],x+dx[i],index); return; } int main(){ cin>>w>>h; if(w>50||h>50){ cout << -1 << endl; return 0; } rep(i,0,h){ string s; cin>>s; v.pb(s); } clr(d,-1); int index = 0; rep(y,0,h){ rep(x,0,w){ if(v[y][x]=='.'&&d[y][x]==-1){ f(y,x,index); index++; } } } if(index!=2){ cout << -1 << endl; return 0; } int mn = 10000; rep(y1,0,h){ rep(x1,0,w){ if(d[y1][x1]==-1)continue; rep(y2,0,h){ rep(x2,0,w){ if(d[y2][x2]==-1)continue; if(d[y1][x1]!=d[y2][x2]){ mn = min(mn,abs(x1-x2)+abs(y1-y2)-1); } } } } } cout << mn << endl; return 0; } /* 2つの空洞を判別してすべての空洞間でマンハッタン距離を調べます。 判別は深さ優先探索やUnion-Findを使っても良いと思います。 ワーシャルフロイドで空洞間の距離が0にならない最小のものを調べる方法もあります。 制約が小さいので他にも幅優先探索などいろいろな解き方があると思います。 3つ以上の空洞にするともう少し難しくなります。 */