Nejkratší cesta z bludiště BFS – C / C++ – Fórum – Programujte.com

Ahoj, snažím se najít nejkratší cestu z bludiště prohledáváním do šířky. Program už projde všechny políčka a najde cíl, tady je kód: 

#include <fstream>
#include <queue>
#include <iostream> 

using std::queue;

struct s_maze
{
	char place;
	int c;
	int r;
	bool used;
};

int main()
{
	using std::ifstream;
	using std::ofstream;

	ifstream fin;
	ofstream fout;

	fin.open("maze.in");
	if (fin.is_open() == false)
		return 0;
	int row, column, start_c, start_r;
	fin >> row >> column;
	
	s_maze maze[50][50];
	s_maze test_maze;
	for (int c = 0; c < column; ++c)
	{
		for (int r = 0; r < row; ++r)
		{
			fin >> maze[c][r].place;
			maze[c][r].used = false;
			maze[c][r].c = c;
			maze[c][r].r = r;
			if (maze[c][r].place == 'S')
			{
				start_c = c;
				start_r = r;
			}
		}
	}
	
	queue <s_maze> q;

	q.push(maze[start_c][start_r]);
	
	while(q.empty() != true)
	{
		test_maze = q.front();
		maze[test_maze.c][test_maze.r].used = true;
		std::cout << test_maze.c <<" " << test_maze.r << std::endl;
		q.pop();
		if (test_maze.place == 'C')
		{
			std::cout << "exit at " << test_maze.c << " " << test_maze.r;
			std::cin.get();
			return 0;
		}
	

	if (test_maze.c - 1 >= 0)
	{	
		if (maze[test_maze.c - 1][test_maze.r].place != '#' && (maze[test_maze.c - 1][test_maze.r].place == '.' || maze[test_maze.c - 1][test_maze.r].place == 'S' || maze[test_maze.c - 1][test_maze.r].place == 'C') && (maze[test_maze.c - 1][test_maze.r].used == 0))
		{
			q.push(maze[test_maze.c - 1][test_maze.r]);
		}
	}




	if (test_maze.c + 1 <= column)
	{
		if (maze[test_maze.c + 1][test_maze.r].place != '#' && (maze[test_maze.c + 1][test_maze.r].place == '.' || maze[test_maze.c + 1][test_maze.r].place == 'S' || maze[test_maze.c + 1][test_maze.r].place == 'C') && (maze[test_maze.c + 1][test_maze.r].used == 0))
		{
			q.push(maze[test_maze.c + 1][test_maze.r]);
		}
	}



	if (test_maze.r + 1 <= row)
	{

		if (maze[test_maze.c][test_maze.r + 1].place != '#' && (maze[test_maze.c][test_maze.r + 1].place == '.' || maze[test_maze.c][test_maze.r + 1].place == 'S' || maze[test_maze.c][test_maze.r + 1].place == 'C') && (maze[test_maze.c][test_maze.r + 1].used == 0))
		{
			q.push(maze[test_maze.c][test_maze.r + 1]);
		}
	}



	if (test_maze.r - 1 >= 0)

	{

		if (maze[test_maze.c][test_maze.r - 1].place != '#' && (maze[test_maze.c][test_maze.r - 1].place == '.' || maze[test_maze.c][test_maze.r - 1].place == 'S' || maze[test_maze.c][test_maze.r - 1].place == 'C') && (maze[test_maze.c][test_maze.r - 1].used == 0))
		{
			q.push(maze[test_maze.c][test_maze.r - 1]);
		}
	}
	
	}







	for (int c = 0; c < column; ++c)
	{
		for (int r = 0; r < row; ++r)
		{
			std::cout << maze[c][r].place;
		}
		std::cout << std::endl;
	}
	std::cout << start_r << "  " << start_c;
	std::cin.get();
	return 0;
}

V tom maze.in je počet sloupců, řádků a bludiště -

8 3
S#....#F
.#.##.#.
........

Dá se nějak vylepšit ten vstup když mám velikost v souboru(abych nemusel používat 50x50 a testovat jestli je tam platný symbol)?

Jak bych měl sledovat cestu? Přemýšlím o lineárním spojovém seznamu ale nevím co dělat když se ty cesty větví - chci vypsat cestu v souřadnicích.

Díky

tak ciste teoreticky bys mohl udelat analyzu bludiste a oznacit si jen pozice uzlu (vetveni) a vzdalenost od predchoziho uzlu a pripadne odkaz na nej...

a pak podobna forma bfs je neco jako ohodnocovani pozic... (aktualni pozice ma vzdalenost 0, a vsechny sousedni kam se da pohnout, das do fronty se vzdalenosti +1... a takhle pokracujes pro kazdou pozici dokud nenarazis na konec...) jo a dobry je neprepisovat si vzdalenosti, pokud bys tam mel mensi cislo nez bys zapsal nove

vypsani cesty by pak bylo pozadu - najit v okoli vzdy o 1 mensi nez aktualne

Zkusil jsem to ohodnocování pozic a funguje to dobře, ale napadá mě - dá se pak nějak dostat i ta zbylá cesta? Myslím jako vypsat všechny cesty z bludiště podle rychlosti(v tom příkladu nahoře nevím jak bych dostal tu delší - horem). Nebo na to bych musel nějak jinak? Díky

musel bys mit u kazdy pozice seznam vsech hodnoceni, ktere se na ni dotaly + mozna ze ktereho smeru (pokud by bylo treba vicekrat 10 ale prislo se z leva, pak z prava, a tak... a asi se vyhnout smerum kde by tydle cisla klesaly (prevence cyklu?) nic trivialniho

trosku lepe by se to delalo na grafu .. ale jen o cast (nebralo by se kazdej bod ale jen ruzny grupy bodu)

To je na mě trochu moc... A nešlo by třeba si jenom určit nějak záchytný body? Příklad - 

S#....#F                       S # 6 7 8 9 # F
.#.##.#.                       1 # 5 # # 10# 10
........      označím jako     2 3 4 5 6 7 8 9
 #.##.#                            5 # # 12
  ..#.                             6 7 # 11     ...                               8 9 10

Tady bych ho udělal na 7 a pak bych šel první cestu a při další skočil na nejnižší možnost (10) a pokračoval po ní a pak znova tu 12. Šlo by to takhle? Určil bych je asi tam kde by se jinak přepisovalo mensi cislo vetsim(ta 7) nebo to tak vychazi jen nahodou?