結果

問題 No.157 2つの空洞
コンテスト
ユーザー IL_msta
提出日時 2015-06-16 10:32:03
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
MLE  
実行時間 -
コード長 2,248 bytes
コンパイル時間 718 ms
コンパイル使用メモリ 89,552 KB
実行使用メモリ 718,792 KB
最終ジャッジ日時 2024-07-06 21:43:09
合計ジャッジ時間 4,412 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 13 MLE * 1 -- * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>

#include <algorithm>
#include <cmath>

#include <string>
#include <list>
#include <queue>
#include <vector>
#include <complex>

/////////
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define P(p) std::cout<<(p)<<std::endl;
/////////
typedef long long LL;
typedef long double LD;
/////////
using namespace::std;
/////////

int main(void){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed;//
    //cout << setprecision(6);//
	
	int W,H;
	cin>>W>>H;
	int fi[20][20];
	char c;
	int y=-1,x;
	rep(h,H)rep(w,W){
		cin>>c;
		if(c=='#'){
			fi[h][w] = -1;
		}else{
			fi[h][w] = 0;
			if(y==-1){
				y=h;
				x=w;
			}
		}
	}
	
	queue< pair<int,int> > qu;
	qu.push( pair<int,int>(y,x) );
	pair<int,int> temp;
	int dy[4] = { 0, 1, 0,-1};
	int dx[4] = { 1, 0,-1, 0};
	while(!qu.empty()){
		temp = qu.front();
		qu.pop();
		fi[temp.first][temp.second] = 1;
		for(int i=0;i<4;++i){
			if( 0 <= temp.first + dy[i] && temp.first + dy[i] < H  &&
				0 <= temp.second + dx[i] && temp.second + dx[i] < W){
				if(fi[temp.first + dy[i]][temp.second + dx[i]] == 0){
					qu.push(pair<int,int>(temp.first + dy[i],temp.second + dx[i]));
				}
			}
		}
	}
	//1と0
	int ans = -1;
	int tempans;
	int tfi[20][20];
	rep(h,H)rep(w,W){
		if( fi[h][w] == 1){
			rep(hh,H)rep(ww,W)tfi[hh][ww] = fi[hh][ww];
			queue< pair<int,int> > quu;
			quu.push(pair<int,int>(h,w));
			//tfi[h][w] = 0;//最後に-1する
			while(!quu.empty()){
				temp = quu.front();
				quu.pop();
				for(int i=0;i<4;++i){
					if( 0 <= temp.first + dy[i] && temp.first + dy[i] < H  &&
						0 <= temp.second + dx[i] && temp.second + dx[i] < W){
						if(tfi[temp.first + dy[i]][temp.second + dx[i]] == -1){
							tfi[temp.first + dy[i]][temp.second + dx[i]] = tfi[temp.first][temp.second] + 1;
							quu.push(pair<int,int>(temp.first + dy[i],temp.second + dx[i]));
						}else if(tfi[temp.first + dy[i]][temp.second + dx[i]] == 0){
							tempans = tfi[temp.first][temp.second] + 1;
							if( ans == -1 || ans > tempans){
								ans = tempans;
							}
							while(!quu.empty())quu.pop();
							break;
						}
					}
				}
			}
		}
	}
	P(ans-2);

	return 0;
}
0