Submission #1998053

---

Source Code Expand

#include <iostream>
#include <string>

#define rep(i,s,e) for (int i = s; i < e; ++i)
using namespace std;

static const int max_size = 51;
int R, C;
string c[max_size];
int Q[100000][2];
bool visited[max_size][max_size];
int min_count[max_size][max_size];
int QP = 0;
int QP_L = 0;

int vx[4] = { 1,0,-1,0 };
int vy[4] = { 0,-1,0,1 };

void bfs(int x, int y) {
	//push queue
	rep(i, 0, 4) {
		if (x + vx[i] >= 1 && x + vx[i] <= R && y + vy[i] >= 1 && y + vy[i] <= C) {
			if (!visited[x + vx[i]][y + vy[i]] && c[x + vx[i]][y + vy[i]] != '#') {
				Q[QP_L][0] = x + vx[i];
				Q[QP_L][1] = y + vy[i];
				visited[x + vx[i]][y + vy[i]] = true;
				QP_L++;

				if (min_count[x + vx[i]][y + vy[i]] > (min_count[x][y] + 1)) {
					min_count[x + vx[i]][y + vy[i]] = min_count[x][y] + 1;
				}
			}
		}
	}

	//Register
	//visited[x][y] = true;
}

int main()
{
	cin >> R >> C;
	int sx, sy; cin >> sx >> sy;
	int gx, gy; cin >> gx >> gy;

	rep(i, 0, R)
	{
		cin >> c[i + 1];
		c[i + 1] = ' ' + c[i + 1];
	}
	rep(i, 0, R)
	{
		rep(j, 0, C)
		{
			min_count[i][j] = 1000000000;
			visited[i][j] = false;
		}
	}

	int count = 0;
	Q[QP][0] = sx;
	Q[QP][1] = sy;
	visited[sx][sy] = true;
	min_count[sx][sy] = 0;
	QP_L++;
	while (true) {
		bfs(Q[QP][0], Q[QP][1]);
		QP++;

		if (Q[QP][0] == gx && Q[QP][1] == gy) {
			break;
		}
	}
	cout << min_count[gx][gy] << endl;;
	return 0;
}

Submission Info

Judge Result