Nejkratší cesta z bludiště BFS – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Kaja
~ Anonymní uživatel
22 příspěvků
10. 10. 2012   #1
-
0
-

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

Nahlásit jako SPAM
IP: 89.190.52.–
Reklama
Reklama
KIIV+42
God of flame
11. 10. 2012   #2
-
0
-

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

Nahlásit jako SPAM
IP: 62.216.147.–
Program vždy dělá to co naprogramujete, ne to co chcete...
Kaja
~ Anonymní uživatel
22 příspěvků
11. 10. 2012   #3
-
0
-

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

Nahlásit jako SPAM
IP: 89.190.52.–
KIIV+42
God of flame
11. 10. 2012   #4
-
0
-

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)

Nahlásit jako SPAM
IP: 62.216.147.–
Program vždy dělá to co naprogramujete, ne to co chcete...
Kaja
~ Anonymní uživatel
22 příspěvků
11. 10. 2012   #5
-
0
-

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?

Nahlásit jako SPAM
IP: 89.190.52.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 53 hostů

Podobná vlákna

Nejkratsi cesta — založil Jardan

Nejkratší slovo ve větě. — založil JaNevimCoDelat

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý