Submission #162135

---

Source Code Expand

#include <iostream>
#include <queue>
#include <complex>

using namespace std;

struct edge {
	int x, y, step;
	edge(int x, int y, int step) : x(x), y(y), step(step) { }
};

int main() {
	int W, H; cin >> H >> W;
	int m[50][50] = {0};
	int sx, sy; cin >> sy >> sx; --sx, --sy;
	int gx, gy; cin >> gy >> gx; --gx, --gy;
	for (int y = 0; y < H; ++y) {
		string str; cin >> str;
		for (int x = 0; x < W; ++x) {
			m[y][x] = str[x] == '#' ? 1 : 0;
		}
	}

	int ans = -1;
	bool f[50][50] = {0};
	queue<edge> Q; Q.push( edge(sx, sy, 0) );
	while ( !Q.empty() ) {
		edge e = Q.front(); Q.pop();

		if (e.x < 0 || e.x >= W || e.y < 0 || e.y >= H) continue;
		if (m[e.y][e.x]) continue;
		if (f[e.y][e.x]) continue; f[e.y][e.x] = true;

		if (e.x == gx && e.y == gy) {
			ans = e.step;
			break;
		}

		Q.push( edge(e.x + 1, e.y, e.step+1) );
		Q.push( edge(e.x - 1, e.y, e.step+1) );
		Q.push( edge(e.x, e.y + 1, e.step+1) );
		Q.push( edge(e.x, e.y - 1, e.step+1) );
	}
	cout << ans << endl;
}

Submission Info

Judge Result