Submission #162585

---

Source Code Expand

#define _GLIBCXX_DEBUG

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <sstream>
#include <functional>
#include <cmath>

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define numof(array) (sizeof (array) / sizeof *(array))

using namespace std;

int r, c, sy, sx, gy, gx;
char tmap[50][50];
int nummap[50][50];
int ans = -1;

void PassFinding(int x, int y, int num)
{
	if (x == gx&&y == gy&&(ans==-1||ans >= num))
	{
		ans = num;
		return;
	}
	if (nummap[y - 1][x - 1] <= num&&nummap[y - 1][x - 1] != -1)
		return;

	nummap[y - 1][x - 1] = num;

	//cout << x - 1 << " " << y - 1 << endl;

	if (tmap[y - 1][x - 2] != '#')
		PassFinding(x - 1, y, num + 1);
	if (tmap[y - 2][x - 1] != '#')
		PassFinding(x, y - 1, num + 1);
	if (tmap[y - 1][x] != '#')
		PassFinding(x + 1, y, num + 1);
	if (tmap[y][x - 1] != '#')
		PassFinding(x, y + 1, num + 1);
}

void solve()
{
	cin >> r >> c;
	cin >> sy >> sx;
	cin >> gy >> gx;
	for (int i = 0; i < r; i++)
	{
		for (int m = 0; m < c; m++)
		{
			cin >> tmap[i][m];
			nummap[i][m] = -1;
		}
	}

	PassFinding(sx, sy, 0);
	cout << ans << endl;
}

int main(void)
{
	solve();
	return 0;
}

Submission Info

Judge Result