Submission #1367889

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define all(c) (c).begin(),(c).end()
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define iter(c) __typeof((c).begin())
#define tr(it,c) for(iter(c) it=(c).begin(); it!=(c).end(); it++)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define pr(a) cout << (a) << endl
typedef long long ll;
typedef pair<int,int> P;
const int MAX=1000000000;
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
 
int main() {
  int n,m,sx,sy,tx,ty;
  cin >> n >> m >> sx >> sy >> tx >> ty;
  sx--;
  sy--;
  tx--;
  ty--;
  string s[n];
  rep(i,n) cin >> s[i];
  int d[n][m];
  rep(i,n) {
    rep(j,m) d[i][j]=MAX;
  }
  queue<P> que;
  que.push(P(sx,sy));
  d[sx][sy]=0;
  int ans=0;
  while(!que.empty()) {
    P p=que.front();
    que.pop();
    int nx=p.first,ny=p.second;
    if(nx==tx && ny==ty) {
      ans=d[nx][ny];
      break;
    }
    rep(i,4) {
      int x=nx+dx[i],y=ny+dy[i];
      if(x>=0 && x<n && y>=0 && y<m) {
        if(d[x][y]==MAX && s[x][y]=='.') {
	  d[x][y]=d[nx][ny]+1;
	  que.push(P(x,y));
        }
      }
    }
  }
  pr(ans);
  return 0;
}

Submission Info

Judge Result