結果

問題 No.157 2つの空洞
ユーザー IL_mstaIL_msta
提出日時 2015-06-16 10:50:18
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,285 bytes
コンパイル時間 908 ms
コンパイル使用メモリ 83,068 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-09-21 03:03:41
合計ジャッジ時間 1,909 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 1 ms
4,376 KB
testcase_12 AC 1 ms
4,384 KB
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 2 ms
4,376 KB
testcase_15 AC 1 ms
4,380 KB
testcase_16 AC 2 ms
4,380 KB
testcase_17 AC 2 ms
4,376 KB
testcase_18 AC 2 ms
4,376 KB
testcase_19 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:52:11: warning: ‘x’ may be used uninitialized in this function [-Wmaybe-uninitialized]
  fi[y][x] = 1;
  ~~~~~~~~~^~~

ソースコード

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) );
	fi[y][x] = 1;
	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();
		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){
					fi[temp.first + dy[i]][temp.second + dx[i]] = 1;
					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