#include<stdio.h>
#include<iostream>
#include<fstream>

using namespace std;

int count = 0;

int lucas(int n)
{
	if (n == 0)
		return 2;
	if (n == 1)
		return 1;

	return lucas(n - 1) + lucas(n - 2);
}

bool sciezka(char** lab, int x, int y, int maxX, int maxY)
{
	count++;
	if (x > maxX || x < 0 || y > maxY || y < 0)
	{
		return false;
	} //granice labiryntu

	if (lab[x][y] == 2)
	{
		return false;
	}; //backtracking

	if (x == 0 && y == 0)
	{
		return true;
	}; //znalezienie wyjscia

	if (lab[x][y] == 2 || lab[x][y] == 0)
	{ return false;
	}//kolejnosc jest wazna

	lab[x][y] = 2; // oznaczenie drogi

	if (sciezka(lab, x + 1, y, maxX, maxY) == true)
	{
		return true;
	}
	if (sciezka(lab, x - 1, y, maxX, maxY) == true)
	{
		return true;
	}
	if (sciezka(lab, x, y + 1, maxX, maxY) == true)
	{
		return true;
	}
	if (sciezka(lab, x, y - 1, maxX, maxY) == true)
	{
		return true;
	} //implementacja pseudokodu

	return false;
}
int main()
{
	std::ifstream file("tab.txt", std::ifstream::in);
	int x, y;
	file >> x >> y;
	char** lab = new char*[x];
	for (int i = 0; i < x; i++)
		*lab = new char[y];

	for (int i = 0; i < x; i++)
	{
		for (int j = 0; j < y; j++)
		{
			file >> lab[i][j];
		}
	}

	if (sciezka(lab, x - 1, y - 1, x, y) == true)

	{
		cout << "udalo sie " << endl;
	};

	for (int i = 0; i < x; ++i)
	{
		for (int j = 0; j < y; ++j)
			cout << +lab[i][j] << " "; //+dla wynikow liczbowych
		cout << "\n";
	}


	cout << count;
	getchar();

	for (int i = 0; i < x; i++)
	{
		delete[] lab[i];
	}

	delete[] lab;

	return 0;
}