Submission #3775132

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int r,c;cin >> r >> c;
	int sy,sx,gy,gx;cin >> sy >> sx >> gy >> gx;
	sy--;
	sx--;
	gy--;
	gx--;
	vector<string> s(r);
	rep(i,r) cin >> s.at(i);
	vector<vector<int>> a(r,vector<int>(c,10000000));
	vector<vector<bool>> b(r,vector<bool>(c,true));
	a[sy][sx]=0;
	b[sy][sx]=false;
	queue<pii> q;
	vector<int> dx={0,-1,0,1};
	vector<int> dy={1,0,-1,0};
	q.push(mp(sy,sx));
	while(!q.empty()){
		pii cur=q.front();
		q.pop();
		rep(i,4){
			int y=cur.first+dy[i],x=cur.second+dx[i];
			if(x>=0 && x<c && y>=0 && y<r && s[y][x]=='.' && b[y][x]){
				a[y][x]=min(a[y][x],a[cur.first][cur.second]+1);
				q.push(mp(y,x));
				b[y][x]=false;
			}
		}
	}
	cout << a[gy][gx] << endl;
}

Submission Info

Judge Result