Zefektivneni hledani cesty – C / C++ – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

Zefektivneni hledani cesty – C / C++ – Fórum – Programujte.comZefektivneni hledani cesty – C / C++ – Fórum – Programujte.com

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
shunkoplex
~ Anonymní uživatel
1 příspěvek
14. 1. 2010   #1
-
0
-

Zdravim. Dokazal by nekdo tohle prepsat do nejake podoby aby to bylo rychlejsi a mene narocny na pamet? Je to vyhledavani nejkratsi cesty ve 2D textovem poli z S do E.



#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXLENGHT 10000



int main(int argc, char** argv) {
int x,y,i,j=0,**vlny,Spocet=0,Epocet=0,sX,sY,eX,eY,mezera=0,*,*;
int zapis=0,hranice=0,wrong = 0;
char buffer[MAXLENGHT],**mapa,c;

printf("Zadejte bludiste:\n");

fgets(buffer,MAXLENGHT,stdin);
x = strlen(buffer)-1;

y = 200;
mapa = (char**)malloc(y * sizeof(char*));

for (i = 0; i < y; i++)
{
mapa[i] = (char*)malloc(x);
if(strlen(buffer)-1 != x)
wrong = 1;
if (hranice == y)
{
mapa = (char**)realloc(mapa, (2*y)*sizeof(char *));
y *= 2;
for (i = hranice; i < y; i++)
{
mapa[i] = (char*)malloc(x);
}
}

strcpy(mapa[i],buffer);
/*printf("%s\n",mapa[i]);*/
for(j=0;j<x;j++)
{
c = mapa[i][j];
if(c != ' ' && c != '*' && c != 'S' && c != 'E' )
{

wrong = 1;
}
if(i==0 || i == y || j == 0 || j == y)
if(c != '*')
wrong = 1;
}

if(fgets(buffer,MAXLENGHT,stdin) == NULL )
break;
/*
if(feof(stdin))
break; */
hranice++;

}
if(wrong == 1){printf("Nespravny vstup.\n");return 0;}

/* printf("%d",hranice);*/
y = hranice +1;

vlny= (int**)malloc(y * sizeof(int*));
for(i=0;i<y;i++)
{
vlny[i] = (int*)malloc(x*sizeof(int));
for(j=0;j<x;j++)
{
switch( mapa[i][j])
{
case ' ':
vlny[i][j]= 0;
mezera++;
break;
case '*' :
vlny[i][j]= -2;
break;
case 'S' :
vlny[i][j]= 1;
Spocet++;
sX = i;
sY = j;
break;
case 'E' :
vlny[i][j]= -3;
Epocet++;
eX = i;
eY = j;
break;
default :

printf("Nespravny vstup.\n");
return 0;

}
}

}
if(Spocet != 1 || Epocet != 1)
{
printf("Nespravny vstup.\n");
return 0;
}

for(i=0;i<y;i++)
free(mapa[i]);

free(mapa);

polex[0] = sX;
poley[0] = sY;


for(i=0;i<=zapis;i++)
{
/*for(j=0;i<zapis;i++)
printf("%d %d\n",polex[zapis],poley[zapis]); */
if(vlny[polex[i]-1][poley[i]] == 0||vlny[polex[i]-1][poley[i]] == -3)
{
zapis++;
polex[zapis] = polex[i]-1;
poley[zapis] = poley[i];
vlny[polex[zapis]][poley[zapis]] = vlny[polex[i]][poley[i]]+1;
}
if(vlny[polex[i]+1][poley[i]] == 0|| vlny[polex[i]+1][poley[i]] == -3)
{
zapis++;
polex[zapis] = polex[i]+1;
poley[zapis] = poley[i];
vlny[polex[zapis]][poley[zapis]] = vlny[polex[i]][poley[i]]+1;
}
if(vlny[polex[i]][poley[i]-1] == 0|| vlny[polex[i]][poley[i]-1] == -3)
{
zapis++;
polex[zapis] = polex[i];
poley[zapis] = poley[i]-1;
vlny[polex[zapis]][poley[zapis]] = vlny[polex[i]][poley[i]] + 1;
}

if(vlny[polex[i]][poley[i]+1] == 0|| vlny[polex[i]][poley[i]+1] == -3)
{
zapis++;
polex[zapis] = polex[i];
poley[zapis] = (poley[i])+1;
vlny[polex[zapis]][poley[zapis]] = vlny[polex[i]][poley[i]]+1;
}


if(vlny[eX][eY] != -3)
{
printf("Potrebny pocet kroku: %d\n",vlny[polex[zapis]][poley[zapis]]-1);
return 0;

}
}
if(vlny[eX][eY] == -3)
{
printf("Cile nelze dosahnout.\n");
return 0;
}
}

Nahlásit jako SPAM
IP: 62.245.86.–
Reklama
Reklama
Bald3rr0
Super člen
14. 1. 2010   #2
-
0
-
Nahlásit jako SPAM
IP: 82.100.0.–
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, 105 hostů

Podobná vlákna

Cesty ke složkám — založil Domo

Cesty k adresarum — založil nobody

Servlety - cesty — založil Solo

Výpis cesty — založil Shadow

Všechny cesty grafem — založil azurit

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ý