Submission #3417974

---

Source Code Expand

#include<bits/stdc++.h>
#define INF -1
#define F first
#define S second
using namespace std;
typedef pair<int,int> P;
int R,C;
char c[55][55];
int mp[55][55];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int bfs(int sy,int sx,int gy,int gx){
  queue<P> que;
  que.push(make_pair(sy,sx));
  mp[sy][sx]=0;
  while(!que.empty()){
    P p = que.front();
    que.pop();
    for(int i=0;i<4;i++){
      int nx = dx[i] + p.S, ny = dy[i] + p.F;
      if(nx < 0 || nx >= C || ny < 0 || ny >= R || c[ny][nx]=='#') continue;
      if(mp[ny][nx]==INF){
        mp[ny][nx]=mp[p.F][p.S]+1;
        que.push(make_pair(ny,nx));
      }
      else if(mp[ny][nx]>mp[p.F][p.S]+1){
        mp[ny][nx]=mp[p.F][p.S]+1;
        que.push(make_pair(ny,nx));
      }
    }
  }
  return mp[gy][gx];
}
                 
int main(){
  int sy,sx;
  int gy,gx;
  
  cin>>R>>C;
  cin>>sy>>sx;
  cin>>gy>>gx;
  for(int i=0;i<R;i++)
    for(int j=0;j<C;j++) cin>>c[i][j];
  
  for(int i=0;i<R;i++)
    for(int j=0;j<C;j++) mp[i][j]=INF;
  
  cout<<bfs(sy-1,sx-1,gy-1,gx-1)<<endl;
  
  return 0;
}

Submission Info

Judge Result