Submission #691666

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i = 0; i < (int)n; ++i)
typedef long long ll;
typedef pair<int,int> Pair;
const ll p = 1e9+7;

int main(){
	int r,c,sy,sx,gy,gx;
	cin>>r>>c>>sy>>sx>>gy>>gx;
	sy--;sx--;gy--;gx--;
	char s[r][c];
	int h[r][c];
	fill(h[0], h[r], -1);
	REP(i,r){
		string t;
		cin>>t;
		REP(j,c){
			s[i][j] = t[j];
		}
	}
	queue<Pair> qu;
	qu.push(make_pair(sy, sx));
	h[sy][sx] = 0;
	while(1){
		Pair p = qu.front();
		if(h[p.first-1][p.second] == -1 && s[p.first-1][p.second] == '.'){
			qu.push(make_pair(p.first-1, p.second));
			h[p.first-1][p.second] = h[p.first][p.second]+1;
		}
		if(h[p.first][p.second-1] == -1 &&s[p.first][p.second-1] == '.'){
			qu.push(make_pair(p.first, p.second-1));
			h[p.first][p.second-1] = h[p.first][p.second]+1;
		}
		if(h[p.first+1][p.second] == -1 &&s[p.first+1][p.second] == '.'){
			qu.push(make_pair(p.first+1, p.second));
			h[p.first+1][p.second] = h[p.first][p.second]+1;
		}
		if(h[p.first][p.second+1] == -1 &&s[p.first][p.second+1] == '.'){
			qu.push(make_pair(p.first, p.second+1));
			h[p.first][p.second+1] = h[p.first][p.second]+1;
		}
		qu.pop();
		if(h[gy][gx] != -1){
			break;
		}
	}
	cout << h[gy][gx] << endl;
	return 0;
}

Submission Info

Judge Result