TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
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;
}
}
