結果

問題 No.157 2つの空洞
コンテスト
ユーザー kongarishisyamo
提出日時 2016-06-02 17:47:19
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 1,928 bytes
コンパイル時間 741 ms
コンパイル使用メモリ 69,256 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-08 05:46:27
合計ジャッジ時間 1,550 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<queue>
#include<string>
#include<cstdlib>
#include<algorithm>

using namespace std;

#define HMAX 20
#define WMAX 20

string map[HMAX];
int W,H;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};

void fill_char(int x,int y,char c){
  char b=map[y][x];
  queue<int> qy,qx;
  qx.push(x);
  qy.push(y);
  map[y][x]=c;
  while(!qx.empty()){
    int nx=qx.front();qx.pop();
    int ny=qy.front();qy.pop();
    for(int i=0;i<4;i++){
      int fy=ny+dy[i];
      int fx=nx+dx[i];
      if(fx>=0&&fx<W&&fy>=0&&fy<H&&map[fy][fx]==b){
	qy.push(fy);
	qx.push(fx);
	map[fy][fx]=c;
      }
    }
  }
}

int length(int x,int y,char g){
  int ret=WMAX*HMAX+1;
  int cmap[HMAX][WMAX];
  queue<int> qy,qx,qc;
  qx.push(x);
  qy.push(y);
  qc.push(1);

  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cmap[i][j]=HMAX*WMAX+1;
    }
  }

  cmap[y][x]=0;
  while(!qx.empty()){
    //cout<<qx.size()<<endl;
    int nx=qx.front();qx.pop();
    int ny=qy.front();qy.pop();
    int nc=qc.front();qc.pop();
    if(map[ny][nx]==g){
      //cout<<ny<<","<<nx<<","<<ret<<","<<nc<<","<<g<<","<<map[ny][nx]<<endl;
      ret=min(ret,cmap[ny][nx]);
    }
    for(int i=0;i<4;i++){
      int fy=ny+dy[i];
      int fx=nx+dx[i];
      if(fx>=0&&fx<W&&fy>=0&&fy<H){
        if(map[fy][fx]=='#'&&cmap[fy][fx]>cmap[ny][nx]+1){
	  qy.push(fy);
	  qx.push(fx);
          qc.push(nc+1);
	  cmap[fy][fx]=cmap[ny][nx]+1;
	}
	else if(map[fy][fx]!='#'&&cmap[fy][fx]>cmap[ny][nx]){
	  qy.push(fy);
	  qx.push(fx);
          qc.push(nc);
	  cmap[fy][fx]=cmap[ny][nx];
	}
      }
    }
  }

  //for(int i=0;i<H;i++){
  //for(int j=0;j<W;j++){
  //cout<<cmap[i][j]<<" ";
  // }
  //cout<<endl;
  //}
    return ret;
}

int main(){

  cin>>W>>H;
  for(int i=0;i<H;i++){
    cin>>map[i];
  }

  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(map[i][j]=='.'){
	fill_char(j,i,'x');
	cout<<length(j,i,'.')<<endl;
	return 0;
      }
    }
  } 
}
0