Sunday, September 30, 2012

Rat in a maze - Backtracking method


#include<stdio.h>
#define ROW 4
#define COL 4

int findpath(int maze[ROW][COL],int path[ROW][COL],int i,int j){
static int found = 0;
if(i==ROW-1 && j==COL-1){
path[i][j] = 1;
found = 1;
return 1;
} else {
if(i<ROW && j<COL &&!found && (maze[i][j] == 1)){
path[i][j] = 1;
if(!findpath(maze,path,i+1,j) && !findpath(maze,path,i,j+1)){
path[i][j] = 0;
}
} else {
return 0;
}
}
}

int main(){
int maze[ROW][COL] = {{1,0,0,0},
                              {1,1,0,1},
                              {0,1,1,1},
                              {1,1,0,1}};
int path[ROW][COL] = {{0,0,0,0},
      {0,0,0,0},
      {0,0,0,0},
      {0,0,0,0}};
int i,j;
findpath(maze,path,0,0);
for(i=0;i<ROW;i++){
for(j=0;j<COL;j++){
printf("%d\t",path[i][j]);
}
printf("\n");
}
return 0;
}

No comments:

Post a Comment