Submission #162940

---

Source Code Expand

#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

#define max(x, y)	(((x) > (y))? (x) : (y))
#define abs(x)		(((x) < 0)? (-1*(x)) : (x))
#define FORI(s, e)		for (int i = (s); i < (e); i++)
#define FOR(i, s, e)	for (int i = (s); i < (e); i++)
#define REP(i, e)		FOR(i, 0, e)
#define sz(a)			(a.size())

//int dp[10000][10000];

using namespace std;

const int INF = 10000;

int R, C, sy, sx, gy, gx;
int d[50][50];
char r[50][50];
typedef pair<int, int> P;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, -1, 0, 1};

int main() {
	int nx, ny;
	queue<P> q;

	cin >> R >> C;
	cin >> sy >> sx;
	cin >> gy >> gx;

	REP(i, R) REP(j, C) {
		cin >> r[i][j];
		d[i][j] = INF;
	}

	q.push(P(sx, sy));
	d[sy][sx] = 0;	

	while (q.size()) {
		P p = q.front();
		q.pop();
		if (p.first == gx && p.second == gy) break;
		REP(i, 4) {
			nx  = p.first + dx[i]; ny = p.second + dy[i];
			if (0 <= nx && nx < R && 0 <= ny && ny <= C && r[ny][nx] == '.' && d[ny][nx] == INF) {
				q.push(P(nx, ny));
				d[ny][nx] = d[p.second][p.first] + 1;
			}
		}
	}

	cout << d[gy][gx] << endl;

	return 0;
}

Submission Info

Judge Result