LAIB 9 Exercise 1: Maze

laib9ex1.c

#include <stdio.h>
#include <stdlib.h>

#define HUMAN '@' //indicates the initial position of a human being
#define CORRIDOR ' ' //represents corridors (empty cells)
#define EXIT '#' //represents exit points
#define TRAMPLED 1 //already been here
#define NOT_TRAMPLED 0

//Check up,left,down,right
int moves[][2]={{0,1},{-1,0},{0,-1},{1,0}};

char **loadAndAllocateMaze(FILE *inputFile, int *width, int *height);
int **allocatePath(int width, int height);
void printSolution(char **maze, int width, int height, int **path);
int chooseOption();
void printOnePath(char **maze, int width, int height, int human_x, int human_y, int **path);
void printAllPaths(char **maze, int width, int height, int human_x, int human_y, int **path);
void printBestPath(char **maze, int width, int height, int human_x, int human_y, int **path);
int findHuman(char **maze, int width, int height, int *x, int *y);
int solve(char **maze, int x, int y, int **path);
void solveAll(char **maze, int x, int y, int width, int height, int **path);
void solveBest(char **maze, int x, int y, int width, int height, int **path, int count, int **bestPath, int bestCount);
void copyPath(int **dest, int **source, int width, int height);

int main(int argc, char** argv) {
    FILE *input=NULL;
    char **maze;
    int width,height,human_x,human_y,i,**path;

    input=fopen(argv[1],"r");
    if(input==NULL){
        printf("ERROR: Couldn't open file %s.\n",argv[1]);
        return -1;
    }

    maze=loadAndAllocateMaze(input,&width,&height);
    if(maze==NULL){
        printf("ERROR: Couldn't load maze on memory.\n",argv[1]);
        return -1;
    }

    if(!findHuman(maze,width,height,&human_x,&human_y)){
        printf("ERROR: Couldn't find our human.\n");
        for(i=0;i<height;i++)free(maze[i]);
        free(maze);
        return -1;
    }

    path=allocatePath(width,height);
    if(path==NULL){
        printf("ERROR: Couldn't allocate memory to store path.\n");
        for(i=0;i<height;i++)free(maze[i]);
        free(maze);
        return -1;
    }

    switch(chooseOption()){
        case 1:
            printOnePath(maze,width,height,human_x,human_y,path);
            break;
        case 2:
            printAllPaths(maze,width,height,human_x,human_y,path);
            break;
        case 3:
            printBestPath(maze,width,height,human_x,human_y,path);
    }

    for(i=0;i<height;i++)free(maze[i]);
    free(maze);

    for(i=0;i<height;i++)free(path[i]);
    free(path);

    return 0;
}

char **loadAndAllocateMaze(FILE *inputFile, int *width, int *height){
    char **maze;
    int w,h,i,j;

    fscanf(inputFile,"%d %d%*c",&h,&w);
    maze=(char**)malloc(sizeof(char*)*h);
    if(maze==NULL)return NULL;
    for(i=0;i<h;i++){
        maze[i]=(char*)malloc(sizeof(char)*(w+1));
        if(maze[i]==NULL){
            for(j=0;j<i;j++)free(maze[j]);
            free(maze);
            return NULL;
        }
        fgets(maze[i],w+2+1,inputFile);
        maze[i][w]='\0';
    }

    *width=w;
    *height=h;

    return maze;
}

void printSolution(char **maze, int width, int height, int **path){
    int i,j;
    for(i=0;i<height;i++) {
        for (j=0;j<width;j++)printf("%c",path[i][j]==TRAMPLED?':':maze[i][j]);
        printf("\n");
    }
    printf("\n");
}

int chooseOption(){
    int command;
    printf("1 - Print one escape path\n2 - Print all escape paths\n");
    printf("3 - Print the shortest escape path\n\nOption number: ");
    scanf("%d",&command);
    return command;
}

int **allocatePath(int width, int height){
    int **path;
    int i,j;
    path=(int**)malloc(sizeof(int*)*height);
    if(path==NULL)return NULL;
    for(i=0;i<height;i++){
        path[i]=(int*)malloc(sizeof(int)*(width));
        if(path[i]==NULL){
            for(j=0;j<i;j++)free(path[j]);
            free(path);
            return NULL;
        }
        for(j=0;j<width;j++)path[i][j]=NOT_TRAMPLED;
    }
    return path;
}

void printOnePath(char **maze, int width, int height, int human_x, int human_y, int **path){
    solve(maze,human_x,human_y,path);
    printSolution(maze,width,height,path);
}

void printAllPaths(char **maze, int width, int height, int human_x, int human_y, int **path){
    solveAll(maze,human_x,human_y,width,height,path);
}

void printBestPath(char **maze, int width, int height, int human_x, int human_y, int **path){
    int **bestPath=allocatePath(width,height);
    if(path==NULL){
        printf("ERROR: Couldn't allocate memory to store the best path.\n");
        return;
    }
    solveBest(maze,human_x,human_y,width,height,path,0,bestPath,-1);
    printSolution(maze,width,height,bestPath);
}

int solve(char **maze, int x, int y, int **path){
    int i;
    for(i=0;i<4;i++)
        switch(maze[y+moves[i][1]][x+moves[i][0]]){
            case EXIT: return 1;
            case CORRIDOR:
                if(path[y+moves[i][1]][x+moves[i][0]]==NOT_TRAMPLED){
                    path[y+moves[i][1]][x+moves[i][0]]=TRAMPLED;
                    if(solve(maze,x+moves[i][0],y+moves[i][1],path))return 1;
                    path[y+moves[i][1]][x+moves[i][0]]=NOT_TRAMPLED;
                }
                break;
        }
    return 0;
}

void solveAll(char **maze, int x, int y, int width, int height, int **path){
    int i;
    for(i=0;i<4;i++)
        switch(maze[y+moves[i][1]][x+moves[i][0]]){
            case EXIT:
                printSolution(maze,width,height,path);
                return;
            case CORRIDOR:
                if(path[y+moves[i][1]][x+moves[i][0]]==NOT_TRAMPLED){
                    path[y+moves[i][1]][x+moves[i][0]]=TRAMPLED;
                    solveAll(maze,x+moves[i][0],y+moves[i][1],width,height,path);
                    path[y+moves[i][1]][x+moves[i][0]]=NOT_TRAMPLED;
                }
                break;
        }
}

void solveBest(char **maze, int x, int y, int width, int height, int **path, int count, int **bestPath, int bestCount){
    int i;
    for(i=0;i<4;i++)
        switch(maze[y+moves[i][1]][x+moves[i][0]]){
            case EXIT:
                if(count<bestCount||bestCount==-1){
                    bestCount=count;
                    copyPath(bestPath,path,width,height);
                }
                return;
            case CORRIDOR:
                if(path[y+moves[i][1]][x+moves[i][0]]==NOT_TRAMPLED){
                    path[y+moves[i][1]][x+moves[i][0]]=TRAMPLED;
                    solveBest(maze,x+moves[i][0],y+moves[i][1],width,height,path,count+1,bestPath,bestCount);
                    path[y+moves[i][1]][x+moves[i][0]]=NOT_TRAMPLED;
                }
                break;
        }
}

int findHuman(char **maze, int width, int height, int *x, int *y){
    int i,j;
    for(i=0;i<height;i++)
        for (j=0;j<width;j++)
            if(maze[i][j]==HUMAN){
                *x=j;
                *y=i;
                return 1;
            }
    return 0;
}

void copyPath(int **dest, int **source, int width, int height){
    int i,j;
    for(i=0;i<height;i++)
        for (j=0;j<width;j++)
            dest[i][j]=source[i][j];
}