結果

問題 No.157 2つの空洞
コンテスト
ユーザー IL_msta
提出日時 2015-06-16 10:32:03
言語 C++11
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=gnu++11 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
MLE  
実行時間 -
コード長 2,248 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,421 ms
コンパイル使用メモリ 108,980 KB
実行使用メモリ 1,305,120 KB
最終ジャッジ日時 2026-03-28 11:51:05
合計ジャッジ時間 5,606 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 13 MLE * 2 -- * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/deque:71,
                 from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/queue:68,
                 from main.cpp:11:
In member function 'void std::deque<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {std::pair<int, int>}; _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >]',
    inlined from 'void std::deque<_Tp, _Alloc>::push_back(value_type&&) [with _Tp = std::pair<int, int>; _Alloc = std::allocator<std::pair<int, int> >]' at /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/stl_deque.h:1621:21,
    inlined from 'void std::queue<_Tp, _Sequence>::push(value_type&&) [with _Tp = std::pair<int, int>; _Sequence = std::deque<std::pair<int, int>, std::allocator<std::pair<int, int> > >]' at /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/stl_queue.h:318:20,
    inlined from 'int main()' at main.cpp:51:9:
/home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/deque.tcc:176:27: warning: 'x' may be used uninitialized [-Wmaybe-uninitialized]
  176 |           _M_push_back_aux(std::forward<_Args>(__args)...);
      |           ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp: In function 'int main()':
main.cpp:36:18: note: 'x' was declared here
   36 |         int y=-1,x;
      |                  ^

ソースコード

diff #
raw source code 

#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