結果

問題 No.157 2つの空洞
コンテスト
ユーザー matsukin1111
提出日時 2019-02-16 15:34:37
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,641 bytes
コンパイル時間 908 ms
コンパイル使用メモリ 99,684 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-22 07:48:51
合計ジャッジ時間 1,652 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <cmath>   
#include<cctype>
#include<string>
#include<set>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include <deque>
#include <utility> 

#define rep(i,m,n) for(int i = m;i < n;++i)
using namespace std;
using ll = long long;
using R = double;
const ll inf = 1LL << 50;
const ll MOD = 1e9 + 7;

string B[22];
int vis[22][22];
int dx[4] = { -1,0,1,0 }, dy[4] = {0,1,0,-1};
int w, h;
int cnt = 0;
vector< vector< pair<int, int> > >wh(2);




void check(int sx,int sy) {
	stack<pair<int, int>>st;
	vis[sy][sx] = 1;
	st.push({sx,sy});
	wh[cnt].push_back({sx,sy});

	while (!st.empty()) {
		int x, y;
		bool ok = 0;
		auto s = st.top();
		tie(x, y) = s;
		rep(d, 0, 4) {
			int xx = x + dx[d];
			int yy = y + dy[d];
			if (0 <= xx && xx <= w - 1 && 0 <= yy && yy <= h - 1) {
				if (vis[yy][xx] == 0 && B[yy][xx] != '#') {
					vis[yy][xx] = 1;
					st.push({xx,yy});
					wh[cnt].push_back({ xx,yy });
					ok = 1;
					break;
				}
			}
		}
		if (!ok) {
			st.pop();
		}

	}
	return;
}




int main() {
	cin >> w >> h;
	rep(i, 0, h)cin >> B[i];

	rep(i, 0, h) {
		rep(j, 0, w) {
			if (B[i][j] == '.' && vis[i][j] == 0 && cnt == 0) {
				check(j,i);
				cnt++;
			}
			else if (B[i][j] == '.' && vis[i][j] == 0 && cnt == 1) {
				check(j, i);
			}
		}
	}


	int ans = 101010;
	rep(i, 0, wh[0].size()) {
		rep(j, 0, wh[1].size()) {
			ans = min(abs(wh[0][i].first - wh[1][j].first) + abs(wh[0][i].second - wh[1][j].second)-1, ans);
		}
	}

	cout << ans << endl;

	return 0;
}
0