結果

問題 No.157 2つの空洞
ユーザー wing3196wing3196
提出日時 2015-02-26 23:40:46
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,139 bytes
コンパイル時間 1,195 ms
コンパイル使用メモリ 78,652 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-23 21:38:39
合計ジャッジ時間 2,218 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 1 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 1 ms
6,940 KB
testcase_06 AC 1 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 2 ms
6,940 KB
testcase_14 AC 2 ms
6,940 KB
testcase_15 AC 2 ms
6,940 KB
testcase_16 AC 2 ms
6,944 KB
testcase_17 AC 1 ms
6,940 KB
testcase_18 AC 2 ms
6,940 KB
testcase_19 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#include<cmath>
#include<queue>
using namespace std;

struct Data{
	int y,x,cost;
	Data(){}
	Data(int _y,int _x,int _cost){
		y=_y; x=_x; cost=_cost;
	}
	bool operator<(const Data &a)const{
		return cost>a.cost;
	}
};

const int dy[4]={-1,0,1,0},dx[4]={0,1,0,-1};

int main(){
	int W,H;
	char fld[20][20];
	priority_queue<Data> q;
	cin>>W>>H;
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			cin>>fld[i][j];
			if(fld[i][j]=='.' && q.empty()) q.push(Data(i,j,0));
		}
	}

	Data q_c;
	bool used[20][20]={};
	while(!q.empty()){
		q_c = q.top(); q.pop();
		//printf("%d,%d,%d\n",q_c.x,q_c.y,q_c.cost);
		if(used[q_c.y][q_c.x]==true) continue;
		used[q_c.y][q_c.x] = true;
		if(fld[q_c.y][q_c.x]=='.' && q_c.cost>0){
			printf("%d\n",q_c.cost); break;
		}
		for(int i=0;i<4;i++){
			int ny,nx;
			ny = q_c.y+dy[i];
			nx = q_c.x+dx[i];
			if(ny<0 || H<=ny || nx<0 || W<=nx) continue;
			Data q_d = Data(ny,nx,q_c.cost);
			if(fld[ny][nx]=='#') q_d.cost++;
			q.push(q_d);
		}
	}
	return 0;
}
0