Submission #691649

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <queue>
#include <tuple>
#include <utility>

const int TOO_BIG = 123456;
int R, C, sy, sx, gy, gx;
char **c;
int **s;

int find(std::queue< std::tuple<int, int, int> > sque) {
	std::tuple<int, int, int> next = sque.front();
	sque.pop();
	int y = std::get<0>(next);
	int x = std::get<1>(next);
	int score = std::get<2>(next);
	if (y == gy && x == gx)
	{
		return score;
	}
	++score;
	for (int j = (j>0?y-1:y); j <= (j<R-1?y+1:y); ++j)
	{
		for (int i = (i>0?x-1:x); i <= (i<C?x+1:x); ++i)
		{
			if (j != y && i != x) {
				continue;
			}
			if (c[j][i] == '.')
			{
				if (s[j][i] > score)
				{
					s[j][i] = score;
					sque.push(std::tuple<int, int, int>(j, i, score));
				}
			}
		}
	}
	--score;
	return find(sque);
}

int main(void)
{
	std::cin >> R >> C >> sy >> sx >> gy >> gx;
	--sy; --sx; --gy; --gx;
	c = new char*[R];
	s = new int*[R];
	for (int i = 0; i < R; ++i)
	{
		c[i] = new char[C];
		s[i] = new int[C];
		for (int j = 0; j < C; ++j)
		{
			s[i][j] = TOO_BIG;
			std::cin >> c[i][j];
		}
	}

	std::queue< std::tuple<int, int, int> > search;
	search.push(std::tuple<int, int, int>(sy, sx, 0));
	s[sy][sx] = 0;
	std::cout << find(search) << std::endl;

	return 0;
}

Submission Info

Judge Result