寝癖頭の解法

小学生の目線から、勉強中の覚え書きを投稿、更新していきます。

AtCoder Problems in C++ #C - 器物損壊!高橋君

AtCoder Regular Contestの過去問から、その提出コードの解答例です。
AtCoderとは、コンテストを通じて、プログラミングやアルゴリズムを学習するサービスです。
atcoder.jp
プログラミングコンテストとは、「与えられた問題をいかに素早く、正確に」解くことができるかを競うものです。
競技プログラミング」を略して、「競プロ」などと呼ばれています。

#C - 器物損壊!高橋君
atcoder.jp

僕が作成、提出したコードは、以下のとおりです。

/*
AtCoder Problems in C++
#C - 器物損壊!高橋君
https://atcoder.jp/contests/arc005/tasks/arc005_3
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using P=pair<int,int>;
int h,w;
int sx,sy,gx,gy;
char c[10000][10000];
const int val=1000000;
const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int a[500][500];
void BFS(void){
  deque<P> deq;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      a[i][j]=val;
    }
  }
  deq.push_front(P(sx,sy));
  a[sx][sy]=0;
  while(deq.size()){
    P p=deq.front();
    deq.pop_front();
    for(int i=0;i<4;i++){
      int nx=p.first+dx[i],ny=p.second+dy[i];
      if(0<=nx && nx<h && 0<=ny && ny<w && a[nx][ny]==val){
        if(c[nx][ny]=='#'){
          a[nx][ny]=a[p.first][p.second]+1;
          deq.push_back(P(nx,ny));
        }else{
          a[nx][ny]=a[p.first][p.second];
          deq.push_front(P(nx,ny));
        }
        if(nx==gx && ny==gy){
          return;
        }
      }
    }
  }
  return;
}
int main(void){
  cin>>h>>w;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cin>>c[i][j];
    }
  }
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(c[i][j]=='s'){
        sx=i;
        sy=j;
      }
      if(c[i][j]=='g'){
        gx=i;
        gy=j;
      }
    }
  }
  BFS();
  if(a[gx][gy]<=2){
    cout<<"YES"<<endl;
  }else{
    cout<<"NO"<<endl;
  }
  return 0;
}

AtCoder Regular Contestは、オンラインジャッジによるプログラミングコンテストです。
コンテストは日本語と英語に対応していて、週末ごとに実施されているみたいです。
https://practice.contest.atcoder.jp/tutorial
アカウントを登録すれば、誰でも参加できます。