[es] - Lavirint & Backtracking

Emp
Podgorica

Član broj: 42014
Poruke: 54
*.crnagora.net.

Profil

^{06.05.2006. u 23:49 - pre 218 meseci}

Pozdrav svima.
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;
}

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.

Odgovor na temu

z@re
Zarko Bulatovic
Split

Član broj: 29849
Poruke: 443
*.cmu.carnet.hr.

+25 Profil

Re: Lavirint & Backtracking

^{07.05.2006. u 03:25 - pre 218 meseci}

Probaj sa nekim standardnim algoritmima za grafove, poput Floyd-Warshall. Taj algoritam koristi matricnu reprezentaciju grafa, tj. matricu susjednosti, i racuna najkraci put izmedju svih "vrhova" u grafu.

Mozes nac dosta literature i kodova onlajn. Ili, cak mislim da je bilo slicnih tema u "Art of Programming" forumima ovdje, pa malo pretrazi.

_{Q: HSP56 Micromodem nece da radi kompjuter ga prepozna a kad treba da se konektujem nece ne daje ni znaka zivota. u cemu je problem.

A: Crko mozda od grmljavine mozda od spanaca. Uglavnom baci ga u WC solju jako povuci vodu. Skupi 5e i uzmi drugi i ne postuj temu na pogresno mesto.}

Odgovor na temu