Problem je sledeci.Treba da napisem rekurzivnu funkciju koja izracunava i vraca duzinu najkraceg puta u lavirintu i stampa najkraci put.
Uradio sam obicno rjesenje.Tj da stigne do kraja lavirinta.Lavirint je dat matricom:pocetak je [0][0] a kraj [m-1][n-1].
Zidovi su oznaceni brojem 0,a slobodan put sa 1.Put kojim prolazis oznacava se sa 2.
Evo "rjesenja":
Code:
#include <stdio.h>
#include <stdlib.h>
#define ROWS 5
#define COLS 12
#define PROSAO 2
struct point{
int x,y;
};
enum Smjer {Gore,Dolje,Lijevo,Desno};
void Alocirajmatricu(int ***x,int rows,int cols){
int i;
*x= (int **)calloc(rows,sizeof(int **));
for(i=0;i<rows;i++)
*(*x+i)=(int *)calloc(cols,sizeof(int));
}
void Popunimatricu(int **x,int rows,int cols){
x[0][0]=1;x[0][1]=1;x[0][2]=0;x[0][3]=1;x[0][4]=1;x[0][5]=0;
x[0][6]=1;x[0][7]=1;x[0][8]=1;x[0][9]=1;x[0][10]=0;x[0][11]=0;
x[1][0]=0;x[1][1]=1;x[1][2]=1;x[1][3]=1;x[1][4]=0;x[1][5]=1;
x[1][6]=1;x[1][7]=0;x[1][8]=1;x[1][9]=0;x[1][10]=0;x[1][11]=1;
x[2][0]=0;x[2][1]=0;x[2][2]=0;x[2][3]=1;x[2][4]=0;x[2][5]=0;
x[2][6]=1;x[2][7]=0;x[2][8]=1;x[2][9]=1;x[2][10]=1;x[2][11]=1;
x[3][0]=1;x[3][1]=1;x[3][2]=1;x[3][3]=1;x[3][4]=1;x[3][5]=1;
x[3][6]=1;x[3][7]=0;x[3][8]=0;x[3][9]=1;x[3][10]=0;x[3][11]=1;
x[4][0]=0;x[4][1]=1;x[4][2]=1;x[4][3]=1;x[4][4]=0;x[4][5]=0;
x[4][6]=1;x[4][7]=1;x[4][8]=1;x[4][9]=1;x[4][10]=0;x[4][11]=1;
}
void stampaj(int **x,int rows,int cols){
int i,j;
for(i=0;i<rows;i++){
for(j=0;j<cols;j++)printf("%d ",x[i][j]);
printf("\n");
}
printf("\n");
}
struct point Susjedni(point pt,Smjer dir){
struct point novipt=pt;
switch(dir){
case Gore: novipt.y++;break;
case Dolje: novipt.y--;break;
case Lijevo: novipt.x--;break;
case Desno: novipt.x++;break;
}
return novipt;
}
int izlaz(point pt){
return (pt.x == ROWS-1 && pt.y == COLS-1 );
}
void markSquare(point pt, int **lavirint){
lavirint[pt.x][pt.y] = PROSAO;
}
void unmarkSquare(point pt, int **lavirint){
lavirint[pt.x][pt.y] = 1;
}
int isMarked(point pt, int **lavirint){
return (lavirint[pt.x][pt.y] == PROSAO);
}
int Zid(point pt,Smjer dir,int **lavirint){
struct point novipt;
novipt=Susjedni(pt,dir);
if ((0>novipt.x) || (novipt.x>=ROWS) || (0>novipt.y) || (novipt.y)>=COLS || (lavirint[novipt.x][novipt.y]==0))
return 1;
else return 0;
}
int Rjesenje(point pt,int **lavirint){
Smjer dir;
if(izlaz(pt)) return 1;
if(isMarked(pt,lavirint)) return 0;
markSquare(pt,lavirint);
for(dir = Gore; dir<=Desno; dir=Smjer(dir+1)){
if(!Zid(pt,dir,lavirint))
if(Rjesenje(Susjedni(pt,dir),lavirint))
return 1;
}
unmarkSquare(pt,lavirint);
return 0;
}
int main()
{
int **lavirint;
int kraj=0;
struct point tacka;
Alocirajmatricu(&lavirint,ROWS,COLS);
Popunimatricu(lavirint,ROWS,COLS);
stampaj(lavirint,ROWS,COLS);
tacka.x=tacka.y=0;
printf("\nRjesenje:\n\n");
if(Rjesenje(tacka,lavirint)){
stampaj(lavirint,ROWS,COLS);
}
else printf("Nema rjesenja!");
system("PAUSE");
return 0;
}
#include <stdio.h>
#include <stdlib.h>
#define ROWS 5
#define COLS 12
#define PROSAO 2
struct point{
int x,y;
};
enum Smjer {Gore,Dolje,Lijevo,Desno};
void Alocirajmatricu(int ***x,int rows,int cols){
int i;
*x= (int **)calloc(rows,sizeof(int **));
for(i=0;i<rows;i++)
*(*x+i)=(int *)calloc(cols,sizeof(int));
}
void Popunimatricu(int **x,int rows,int cols){
x[0][0]=1;x[0][1]=1;x[0][2]=0;x[0][3]=1;x[0][4]=1;x[0][5]=0;
x[0][6]=1;x[0][7]=1;x[0][8]=1;x[0][9]=1;x[0][10]=0;x[0][11]=0;
x[1][0]=0;x[1][1]=1;x[1][2]=1;x[1][3]=1;x[1][4]=0;x[1][5]=1;
x[1][6]=1;x[1][7]=0;x[1][8]=1;x[1][9]=0;x[1][10]=0;x[1][11]=1;
x[2][0]=0;x[2][1]=0;x[2][2]=0;x[2][3]=1;x[2][4]=0;x[2][5]=0;
x[2][6]=1;x[2][7]=0;x[2][8]=1;x[2][9]=1;x[2][10]=1;x[2][11]=1;
x[3][0]=1;x[3][1]=1;x[3][2]=1;x[3][3]=1;x[3][4]=1;x[3][5]=1;
x[3][6]=1;x[3][7]=0;x[3][8]=0;x[3][9]=1;x[3][10]=0;x[3][11]=1;
x[4][0]=0;x[4][1]=1;x[4][2]=1;x[4][3]=1;x[4][4]=0;x[4][5]=0;
x[4][6]=1;x[4][7]=1;x[4][8]=1;x[4][9]=1;x[4][10]=0;x[4][11]=1;
}
void stampaj(int **x,int rows,int cols){
int i,j;
for(i=0;i<rows;i++){
for(j=0;j<cols;j++)printf("%d ",x[i][j]);
printf("\n");
}
printf("\n");
}
struct point Susjedni(point pt,Smjer dir){
struct point novipt=pt;
switch(dir){
case Gore: novipt.y++;break;
case Dolje: novipt.y--;break;
case Lijevo: novipt.x--;break;
case Desno: novipt.x++;break;
}
return novipt;
}
int izlaz(point pt){
return (pt.x == ROWS-1 && pt.y == COLS-1 );
}
void markSquare(point pt, int **lavirint){
lavirint[pt.x][pt.y] = PROSAO;
}
void unmarkSquare(point pt, int **lavirint){
lavirint[pt.x][pt.y] = 1;
}
int isMarked(point pt, int **lavirint){
return (lavirint[pt.x][pt.y] == PROSAO);
}
int Zid(point pt,Smjer dir,int **lavirint){
struct point novipt;
novipt=Susjedni(pt,dir);
if ((0>novipt.x) || (novipt.x>=ROWS) || (0>novipt.y) || (novipt.y)>=COLS || (lavirint[novipt.x][novipt.y]==0))
return 1;
else return 0;
}
int Rjesenje(point pt,int **lavirint){
Smjer dir;
if(izlaz(pt)) return 1;
if(isMarked(pt,lavirint)) return 0;
markSquare(pt,lavirint);
for(dir = Gore; dir<=Desno; dir=Smjer(dir+1)){
if(!Zid(pt,dir,lavirint))
if(Rjesenje(Susjedni(pt,dir),lavirint))
return 1;
}
unmarkSquare(pt,lavirint);
return 0;
}
int main()
{
int **lavirint;
int kraj=0;
struct point tacka;
Alocirajmatricu(&lavirint,ROWS,COLS);
Popunimatricu(lavirint,ROWS,COLS);
stampaj(lavirint,ROWS,COLS);
tacka.x=tacka.y=0;
printf("\nRjesenje:\n\n");
if(Rjesenje(tacka,lavirint)){
stampaj(lavirint,ROWS,COLS);
}
else printf("Nema rjesenja!");
system("PAUSE");
return 0;
}
Ali to stampa samo jedan put(ne najkraci) do izlaza.
Kako napraviti da stampa najkraci put?I zasto nece da "zakoraci",tj da napise broj 2 na izlazu iz lavirinta tj na [m-1][n-1]?
Svaka pomoc i sugestija dobrodsla.