Submission #162417

---

Source Code Expand

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <stack>
#include <queue>
#include <cctype>
#include <complex>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <cassert>
#include <iomanip>

using namespace std;

#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
typedef long long ll;
typedef complex<int> P;
typedef pair<int,int> pii;
const double EPS = 1e-10;
const double PI  = acos(-1.0);



bool solve(){
	int r, c;
	P s, g;
	cin>> r>> c>> s.imag()>> s.real()>> g.imag()>> g.real();
	s = s + P(-1, -1);
	g = g + P(-1, -1);
	vector<vector<int> > a(r, vector<int>(c));
	for(int i=0;i<r;i++) for(int j=0;j<c;j++){
		char in;
		cin>> in;
		if(in == '.') a[i][j] = -1;
		if(in == '#') a[i][j] = -2;
	}

	queue<P> Q;
	Q.push(s);
	a[s.imag()][s.real()] = 0;
	P dd[4] = {P(0,1), P(1,0), P(-1,0), P(0,-1)};
	while(true){
		P p = Q.front();
		Q.pop();
//		cout<< " "<< p.real()<< " "<< p.imag()<< endl;
		if(p == g) break;
		for(int i=0;i<4;i++){
			P nex = p + dd[i];
			int x = nex.real(), y = nex.imag();
			if(0 <= x && x < c && 0 <= y && y < r && a[y][x] == -1){
				a[y][x] = a[p.imag()][p.real()] + 1;
				Q.push(nex);
			}
		}
	}
	
	cout<< a[g.imag()][g.real()]<< endl;
	return true;
}

int main(){
	cout.setf(ios::fixed);
	cout.precision(10);
	
	solve();
	return 0;
}

 

Submission Info

Judge Result