Labirinth

#include <fstream>
#include <queue>
#include <vector>

using namespace std;

int main()
{
	fstream fin("maze.in");
	ofstream fout("maze.out");
	short int M, N;
	fin >> M >> N;
	pair<short int, short int> start, end;
	fin >> start.first >> start.second >> end.first >> end.second;
	queue<pair<short int, short int>> Maze;
	bool** arr = new bool*[M + 2];
	for (size_t i = 0; i < M + 2; i++)
	{
		arr[i] = new bool[N + 2];
	}

	for (size_t i = 0; i < M + 2; i++)
	{
		for (size_t j = 0; j < N + 2; j++)
		{
			if (i == 0 || j == 0 || i == M + 1 || j == N + 1)
				arr[i][j] = 0;
			else
				fin >> arr[i][j];
		}
	}
	Maze.push(start);
	/*vector<vector<char>> p;
	p.assign(M + 2, vector<char>(N + 2));*/
	char** p = new char*[M + 2];
	for (size_t i = 0; i < M + 2; i++)
	{
		p[i] = new char[N + 2];
	}
	p[start.first][start.second] = -1;
	while (!Maze.empty())
	{
		pair<short int, short int> tmp = Maze.front();
		short int i = tmp.first, j = tmp.second;
		if (arr[i + 1][j] == 1)
		{
			Maze.push(pair<short int, short int>(i + 1, j));
			p[i + 1][j] = '1';
		}
		if (arr[i - 1][j] == 1)
		{
			Maze.push(pair<short int, short int>(i - 1, j));
			p[i - 1][j] = '2';
		}
		if (arr[i][j + 1] == 1)
		{
			Maze.push(pair<short int, short int>(i, j + 1));

			p[i][j + 1] = '3';
		}
		if (arr[i][j - 1] == 1)
		{
			Maze.push(pair<short int, short int>(i, j - 1));
			p[i][j - 1] = '4';
		}
		arr[i][j] = 0;
		Maze.pop();
	}
	if (arr[end.first][end.second] != 0)
		fout << -1 << endl;
	else
	{
		vector<pair<short int, short int>> path;
		int count = 0;
		char tmp = p[end.first][end.second];
		for (pair<short int, short int> i = end;;)
		{
			//path.push_back(i);
			p[i.first][i.second] = tmp;
			if (i == start)
				break;
			if (p[i.first][i.second] == '1')
				{
					i = pair<short int, short int>(i.first - 1, i.second);
					tmp = 2;
				}
			else if (p[i.first][i.second] == '2')
				{
					i = pair<short int, short int>(i.first + 1, i.second);
					tmp = '1';
				}
			else if (p[i.first][i.second] == '3')
				{
					i = pair<short int, short int>(i.first, i.second - 1);
					tmp = '4';
				}
			else if (p[i.first][i.second] == '4')
				{
					i = pair<short int, short int>(i.first, i.second + 1);
					tmp = '3';
				}
			++count;
		}
		for (pair<short int, short int> i = start;;)
		{
			//path.push_back(i);
			fout<<i.first<<" "<<i.second<<endl;
			if (i == end)
				break;
			if (p[i.first][i.second] == '1')
				i = pair<short int, short int>(i.first - 1, i.second);
			else if (p[i.first][i.second] == '2')
				i = pair<short int, short int>(i.first + 1, i.second);
			else if (p[i.first][i.second] == '3')
				i = pair<short int, short int>(i.first, i.second - 1);
			else if (p[i.first][i.second] == '4')
				i = pair<short int, short int>(i.first, i.second + 1);

		}
		reverse(path.begin(), path.end());
		fout << count << endl;
		for (size_t i = 0; i < path.size(); i++)
		{
			fout << path[i].first << " " << path[i].second << endl;
		}
	}


	for (size_t i = 0; i < M + 2; i++)
	{
		delete[] arr[i];
		delete[] p[i];
	}
	delete[] p;
	delete[] arr;
	return 0;
}