結果

問題 No.157 2つの空洞
ユーザー imulanimulan
提出日時 2016-02-08 19:59:49
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,687 bytes
コンパイル時間 1,925 ms
コンパイル使用メモリ 167,940 KB
実行使用メモリ 4,348 KB
最終ジャッジ日時 2023-10-21 20:24:59
合計ジャッジ時間 2,364 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(i=0;i<n;++i)
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); itr++)
#define mp make_pair
#define pb push_back
#define fi first
#define sc second

typedef struct{
  int x,y;
}point;

int main(int argc, char const *argv[]) {
  int i,j;
  int dx[4]={1,0,-1,0};
  int dy[4]={0,-1,0,1};

  //input
  int w,h;
  cin >>w >>h;
  vector<string> f(h);
  rep(i,h) cin >>f[i];

  //最初に見つかった点
  point a;
  bool found=false;
  rep(i,h){
    rep(j,w){
      if(f[i][j]=='.'){
        a.y=i;
        a.x=j;
        found=true;
        break;
      }
    }
    if(found) break;
  }
  //ここからBFS
  queue<point> que;
  que.push(a);
  f[a.y][a.x]='a';
  while (!que.empty()){
    point v=que.front();
    que.pop();
    rep(i,4){
      int nx=v.x+dx[i], ny=v.y+dy[i];
      if(0<=nx&&nx<w && 0<=ny&&ny<h && f[ny][nx]=='.'){
        f[ny][nx]='a';
        point tmp;
        tmp.x=nx;
        tmp.y=ny;
        que.push(tmp);
      }
    }
  }

  //次に見つかった点
  point b;
  found=false;
  rep(i,h){
    rep(j,w){
      if(f[i][j]=='.'){
        b.y=i;
        b.x=j;
        found=true;
        break;
      }
    }
    if(found) break;
  }
  //ここからBFS
  que.push(b);
  f[b.y][b.x]='b';
  while (!que.empty()){
    point v=que.front();
    que.pop();
    rep(i,4){
      int nx=v.x+dx[i], ny=v.y+dy[i];
      if(0<=nx&&nx<w && 0<=ny&&ny<h && f[ny][nx]=='.'){
        f[ny][nx]='b';
        point tmp;
        tmp.x=nx;
        tmp.y=ny;
        que.push(tmp);
      }
    }
  }

  /*
  printf("\n");
  rep(i,h) cout<<f[i]<<endl;
  printf("\n");
  */

  //aの位置から#上を辿ってbに辿り着く距離をそれぞれのaにおいて計算
  const int INF=10000000;
  int ans=INF;
  for(int Y=0; Y<h; ++Y){
    for(int X=0; X<w; ++X){
      if(f[Y][X]!='a') continue;

      int d[20][20];
      rep(i,20)rep(j,20) d[i][j]=INF;
      d[Y][X]=0;

      queue<point> q;
      point st;
      st.x=X;
      st.y=Y;
      q.push(st);
      while(!q.empty()){
        point v=q.front();
        q.pop();
        rep(i,4){
          int nx=v.x+dx[i], ny=v.y+dy[i];
          if(0<=nx&&nx<w && 0<=ny&&ny<h && f[ny][nx]!='a' && d[ny][nx]>d[v.y][v.x]+1){

            d[ny][nx]=d[v.y][v.x]+1;
            if(f[ny][nx]=='b'){
              ans=min(ans,d[ny][nx]-1);
              //printf("%d, %d %d\n",ans,ny,nx);
            }
            else{
              point tmp;
              tmp.x=nx;
              tmp.y=ny;
              q.push(tmp);
            }
          }
        }
      }

    }
  }

  std::cout << ans << std::endl;
  return 0;
}
0