Submission #1687184

---

Source Code Expand

#include<iostream>
#include<queue>
using namespace std;

const int INF=100000000;

char maze[50][51];
int R, C;
int sx, sy;
int gx, gy;

int d[50][50];

int dx[4]={1, 0, -1, 0}, dy[4]={0, 1, 0, -1};


int bfs(){
  queue< pair<int, int> > que;

  for(int i=0;i<R;i++) for(int j=0;j<C;j++) d[i][j]=INF;

  que.push(pair<int, int>(sy, sx));
  d[sy][sx]=0;

  while(que.size()){
    pair<int, int> p=que.front();
    que.pop();

    if(p.first==gy&&p.second==gx) break;

    for(int i=0;i<4;i++){
      int ny=p.first+dy[i], nx=p.second+dx[i];

      if(0<=ny&&ny<R&&0<=nx&&nx<C&&maze[ny][nx]!='#'&&d[ny][nx]==INF){
        que.push(pair<int, int>(ny, nx));
        d[ny][nx]=d[p.first][p.second]+1;
      }
    }
  }
  return d[gy][gx];
}

int main(){

  cin>>R>>C;
  cin>>sy>>sx;
  cin>>gy>>gx;
  sy--;sx--;gy--;gx--;
  for(int i=0;i<R;i++) for(int j=0;j<C;j++) cin>>maze[i][j];

  int res=bfs();

  cout<<res<<endl;

  return 0;
}

Submission Info

Judge Result