Submission #691214

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef pair<LL, LL> PLL;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;

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

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int H, W; cin >> H >> W;
  int sy, sx; cin >> sy >> sx;
  int gy, gx; cin >> gy >> gx;
  VS vs(H);
  REP(y,H) cin >> vs[y];
  VVI dist(H, VI(W,-1));
  --sy, --sx, --gy, --gx;
  dist[sy][sx] = 0;
  queue<PII> q;
  q.push(MP(sx,sy));
  while(!q.empty()){
	auto p = q.front(); q.pop();
	REP(i,4){
	  int tx = p.FF + dx[i];
	  int ty = p.SS + dy[i];
	  if(tx < 0 || W <= tx || ty < 0 || H <= ty || vs[ty][tx] == '#' || dist[ty][tx] >= 0) continue;
	  dist[ty][tx] = dist[p.SS][p.FF] + 1;
	  q.push(MP(tx,ty));
	}
  }

  cout << dist[gy][gx] << endl;
  
  return 0;
}

Submission Info

Judge Result