Submission #1337877

---

Source Code Expand

//#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#define MOD 1000000007
#define INF (1LL<<30)
#define LLINF (1LL<<60)
#define PI 3.14159265359
#define EPS 1e-12
//#define int ll

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

string s[55];
int d[55][55];
signed main(void)
{
	int h, w;
	cin >> h >> w;
	int sy, sx, gy, gx;
	cin >> sy >> sx >> gy >> gx;
	sx--, sy--, gx--, gy--;
	REP(i, h) cin >> s[i];

	queue<PII> q;
	REP(i, h) REP(j, w) d[i][j] = INF;
	q.push(PII(sx, sy));
	d[sy][sx] = 0;

	while(q.size()) {
		PII p = q.front(); q.pop();
		if(p.first == gx && p.second == gy) break;
		REP(i, 4) {
			int nx = p.first + dx[i], ny = p.second + dy[i];
			if(IN(0, h, ny) && IN(0, w, nx) && s[ny][nx] != '#' && d[ny][nx] == INF) {
				q.push(PII(nx, ny));
				d[ny][nx] = d[p.second][p.first] + 1;
			}
		}
	}
	/*REP(i, h) {
		REP(j, w) {
			cout << d[i][j] << " ";
		}
		cout << endl;
	}*/
	cout << d[gy][gx] << endl;

	return 0;
}

Submission Info

Judge Result