結果

問題 No.157 2つの空洞
ユーザー wing3196wing3196
提出日時 2015-02-26 23:40:46
言語 C++11
(gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

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