Submission #1212012

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define INF 2000000000
#define MOD 1000000007
typedef long long ll;
typedef pair<int, int> P;


int main()
{
	int r, c, sy, sx, gy, gx;
	cin >> r >> c >>  sy >> sx >> gy >> gx;
	sy--;
	sx--;
	gy--;
	gx--;
	vector<string> cc(r);
	for (int i = 0; i < r; i++) {
		cin >> cc[i];
	}

	int memo[r][c];
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			memo[i][j] = 0;
		}
	}
	queue<P> q;
	q.push(P(sy,sx));
	int cnt=0;
	while (true) {
		cnt++;
		int loop = q.size();
		for (int ii = 0; ii < loop; ii++) {
			P p = q.front();q.pop();
			if (memo[p.first][p.second]>0) {
				continue;
			}
//			cout << p.first << " " << p.second << "\n";
			memo[p.first][p.second]++;
			if (p.first==gy&&p.second==gx) {
				cout << cnt-1 << "\n";
				return 0;
			}
			if (p.first>0&&cc[p.first-1][p.second]!='#') {
				q.push(P(p.first-1,p.second));
			}
			if (p.first<r-1&&cc[p.first+1][p.second]!='#') {
				q.push(P(p.first+1,p.second));
			}
			if (p.second>0&&cc[p.first][p.second-1]!='#') {
				q.push(P(p.first,p.second-1));
			}
			if (p.first<c-1&&cc[p.first][p.second+1]!='#') {
				q.push(P(p.first,p.second+1));
			}
		}

//		cout << cnt << "\n";
	}
}

Submission Info

Judge Result