chacoderのブログ

競技プログラミングそのほか

トップ > ABC176D

ABC176D


atcoder.jp

一昨日のＡＢＣ１７６Ｄ　Wizard in Mazeにトライしました。
怖がって手をださないでいると永久に怖いので思い切って書いてみました。

検討１

自力で考えて書いてますがどうにも解けません。
もう少し悩みます。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>P;
long long MAX=1000000000;
char D[1010][1010];
int E[1010][1010];
int H,W;
int CH,CW;
int DH,DW;
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};

int bfs(int x,int y){
  E[x][y]=0;
  deque<P>que;
  que.push_front(P(x,y));
  
  while(que.size()){
    P p=que.front();que.pop_front();
    //cout<<p.first<<"***"<<p.second<<endl;
    
  
    for(int i=0;i<4;i++){
      int nx=p.first+dx[i],ny=p.second+dy[i];
        //コスト０で移動できる場合フロントに挿入する
      if(D[nx][ny]=='.' && E[nx][ny]==MAX && 1<=nx && nx<=H && 1<=ny && ny<=W){
          que.push_front(P(nx,ny));
          E[nx][ny]=E[p.first][p.second];
       // cout<<nx<<" "<<ny<<"!"<<E[nx][ny]<<endl;
      }
    }
    
    //５×５を探索する
    //cout<<"###"<<endl;
    for(int j=p.first-1;j<=p.first+2;j++){
      for(int k=p.second-2;k<=p.second+2;k++){
        if(1<=j && j<=H && 1<=k && k<=W && E[j][k]==MAX && D[j][k]=='.'){
          que.push_back(P(j,k));
          E[j][k]=min(E[j][k],E[p.first][p.second]+1);
        }
      }
    }

  }
  return 0;
}

int main(){
  cin>>H>>W;
  cin>>CH>>CW;
  cin>>DH>>DW;
  
  //Eを最大値で初期化
  for(int i=0;i<1005;i++){
    for(int j=0;j<1005;j++){
      E[i][j]=MAX;
    }
  }
  
  //グリッド入力
  for(int i=1;i<=H;i++){
    for(int j=1;j<=W;j++){
      cin>>D[i][j];
    }
  }
  
  bfs(CH,CW);
  if(E[DH][DW]==MAX){
    cout<<-1<<endl;
  }
  else{
    cout<<E[DH][DW]<<endl;
  }
  return 0;
}

検討２

coutデバッグで追いかけたみたところ、先にワープを使ってE[DH][DW]が1以上になっている場合にあとから隣接で更新していないことがわかりました。

コードを一部書き換えて
変更前　E[nx][ny] == MAX
変更後　E[nx][ny] > E[p.first][p.second]
これでどうか。

だいぶよくなったけれどWAが１ケースだけ残りました(XX)。
もう少し悩みます。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>P;
long long MAX=1000000000;
char D[1010][1010];
int E[1010][1010];
int H,W;
int CH,CW;
int DH,DW;
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};

int bfs(int x,int y){
  E[x][y]=0;
  deque<P>que;
  que.push_front(P(x,y));
  
  while(que.size()){
    P p=que.front();que.pop_front();
    //cout<<p.first<<"***"<<p.second<<endl;
    
  
    for(int i=0;i<4;i++){
      int nx=p.first+dx[i],ny=p.second+dy[i];
        //コスト０で移動できる場合フロントに挿入する
      if(D[nx][ny]=='.' && E[nx][ny]>E[p.first][p.second] && 1<=nx && nx<=H && 1<=ny && ny<=W){
          que.push_front(P(nx,ny));
          E[nx][ny]=E[p.first][p.second];
       //cout<<nx<<" "<<ny<<"!"<<E[nx][ny]<<endl;
      }
    }
    
    //５×５を探索する
    //cout<<"###"<<endl;
    for(int j=p.first-1;j<=p.first+2;j++){
      for(int k=p.second-2;k<=p.second+2;k++){
        if(1<=j && j<=H && 1<=k && k<=W && E[j][k]==MAX && D[j][k]=='.'){
          que.push_back(P(j,k));
          E[j][k]=min(E[j][k],E[p.first][p.second]+1);
        }
      }
    }

  }
  return 0;
}

int main(){
  cin>>H>>W;
  cin>>CH>>CW;
  cin>>DH>>DW;
  
  //Eを最大値で初期化
  for(int i=0;i<1005;i++){
    for(int j=0;j<1005;j++){
      E[i][j]=MAX;
    }
  }
  
  //グリッド入力
  for(int i=1;i<=H;i++){
    for(int j=1;j<=W;j++){
      cin>>D[i][j];
    }
  }
  
  bfs(CH,CW);
  if(E[DH][DW]==MAX){
    cout<<-1<<endl;
  }
  else{
    cout<<E[DH][DW]<<endl;
  }
  return 0;
}

検討３

こんなグリッド入力でよく通ってたなと驚きました。
charなのでこれでいいのですね。
おまじない含みでいつもの形に直し、さらに座標を０オリジンにしてみました。
しかし相変わらず１ケースＷＡとれません。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>P;
long long MAX=1000000000;
char D[1010][1010];
int E[1010][1010];
int H,W;
int CH,CW;
int DH,DW;
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};

int bfs(int x,int y){
  E[x][y]=0;
  deque<P>que;
  que.push_front(P(x,y));
  
  while(que.size()){
    P p=que.front();que.pop_front();
    //cout<<p.first<<"***"<<p.second<<endl;
    
  
    for(int i=0;i<4;i++){
      int nx=p.first+dx[i],ny=p.second+dy[i];
        //コスト０で移動できる場合フロントに挿入する
      if(D[nx][ny]=='.' && E[nx][ny]>E[p.first][p.second] && 0<=nx && nx<H && 0<=ny && ny<W){
          que.push_front(P(nx,ny));
          E[nx][ny]=E[p.first][p.second];
       //cout<<nx<<" "<<ny<<"!"<<E[nx][ny]<<endl;
      }
    }
    
    //５×５を探索する
    //cout<<"###"<<endl;
    for(int j=p.first-1;j<=p.first+2;j++){
      for(int k=p.second-2;k<=p.second+2;k++){
        if(0<=j && j<H && 0<=k && k<W && E[j][k]>E[p.first][p.second]+1 && D[j][k]=='.'){
          que.push_back(P(j,k));
          E[j][k]=E[p.first][p.second]+1;
        }
      }
    }
  }
  return 0;
}

int main(){
  cin>>H>>W;
  cin>>CH>>CW;
  CH--;CW--;
  cin>>DH>>DW;
  DH--;DW--;
  
  //Eを最大値で初期化
  for(int i=0;i<1005;i++){
    for(int j=0;j<1005;j++){
      E[i][j]=MAX;
    }
  }
  
  //グリッド入力
  string S;
  for(int i=0;i<H;i++){
    cin>>S;    
    for(int j=0;j<W;j++){
      D[i][j]=S.at(j);
    }
  }
  
  bfs(CH,CW);
  if(E[DH][DW]==MAX){
    cout<<-1<<endl;
  }
  else{
    cout<<E[DH][DW]<<endl;
  }
  return 0;
}

検討４

あった！ここが間違ってた！！

誤 for(int j=p.first-1;j<=p.first+2;j++){

正　for(int j=p.first-2;j<=p.first+2;j++){

無事ＡＣしました！

https://atcoder.jp/contests/abc176/submissions/16207155