Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /******
- MAIN3.C
- ******/
- #include <stdio.h>
- #include <stdlib.h>
- #define C1 1 /* C1 E1 C2 */
- #define C2 2 /* */
- #define C3 3 /* E2 M E3 */
- #define C4 4 /* */
- /* C3 E4 C4 */
- #define E1 5
- #define E2 6
- #define E3 7
- #define E4 8
- #define M 9
- //-----------
- #define DEPTH 8
- typedef struct path
- {
- char path[DEPTH+1];
- char taken[10];
- int index;
- }t_path;
- /* PROTOTYPES */
- void drawpattern(t_path*);
- void pathfinder(t_path* current_path, int depth);
- void addToPath(t_path* p, char toAdd);
- void moveCursor(int, int);
- void drawTakenMap(t_path* p);
- void updateTakenMap(t_path* p);
- //------- NEEEWWWWWW-------
- char iHaveBeenThere[10000];
- int main(){
- t_path* my_path = (t_path*)malloc(sizeof(t_path));
- int i;
- for(i=1;i<=9;i++){
- my_path->taken[i] = 0;
- }
- my_path->index = 0;
- my_path->path[0] = C1;
- my_path->taken[C1] = 1;
- //t_path** pathList = malloc(10000*sizeof(t_path*));
- pathfinder(my_path, 0);
- drawpattern(my_path);
- return 0;
- }
- void pathfinder(t_path* current_path, int depth){
- int k;
- /*printf("\n");
- for(k=0; k<depth; k++){
- printf(" ");
- }
- printf("Called : depth:%d | ", depth);
- drawpattern(current_path);
- for(k=0; k<depth; k++){
- printf(" ");
- }
- drawTakenMap(current_path);*/
- if(depth==DEPTH){ //Depth Touched !
- //printf("---------\nDepth touched\n");
- drawpattern(current_path);
- //drawTakenMap(current_path);
- current_path->index--;
- current_path->taken[current_path->path[current_path->index]]=0;
- return;
- }
- //printf("called index:%d\n", current_path->index);
- int i = 0;
- int check = 0;
- char init = current_path->path[current_path->index];//The init part is the last element of the path
- if(init==C1){
- if(current_path->taken[E1]==0) //If E1 is not taken
- {
- addToPath(current_path, E1);
- pathfinder(current_path, depth+1);
- }
- if (current_path->taken[E2]==0) // E1 is taken so we check if E2 is taken
- {
- addToPath(current_path, E2);
- pathfinder(current_path, depth+1);
- }
- if (current_path->taken[E3]==0) // E2 is taken so we check if E3 is taken
- {
- addToPath(current_path, E3);
- pathfinder(current_path, depth+1);
- }
- if (current_path->taken[E4]==0) // E2 is taken so we check if E3 is taken
- {
- addToPath(current_path, E4);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[M]==0)
- {
- addToPath(current_path, M);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[E1]==1 && current_path->taken[C2]==0) //Jump condition
- {
- addToPath(current_path, C2);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[E2]==1 && current_path->taken[C3]==0) //Jump condition
- {
- addToPath(current_path, C3);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[M]==1 && current_path->taken[C4]==0) //Jump condition M->C4
- {
- addToPath(current_path, C4);
- pathfinder(current_path, depth+1);
- }
- // there is no way possible, STOP (In fact we can take into account the jump)
- //printf("No possible from C1\n");
- //drawpattern(current_path);
- current_path->path[current_path->index] = 0;
- current_path->index--;
- updateTakenMap(current_path);
- return;
- }
- if(init==C2){
- if(current_path->taken[E1]==0) //If E1 is not taken
- {
- addToPath(current_path, E1);
- pathfinder(current_path, depth+1);
- }
- if (current_path->taken[E3]==0) // E1 is taken so we check if E3 is taken
- {
- addToPath(current_path, E3);
- pathfinder(current_path, depth+1);
- }
- if (current_path->taken[E2]==0)
- {
- addToPath(current_path, E2);
- pathfinder(current_path, depth+1);
- }
- if (current_path->taken[E4]==0)
- {
- addToPath(current_path, E4);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[M]==0)
- {
- addToPath(current_path, M);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[E2]==1 && current_path->taken[C1]==0) //Jump condition
- {
- addToPath(current_path, C1);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[E4]==1 && current_path->taken[C4]==0) //Jump condition
- {
- addToPath(current_path, C4);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[M]==1 && current_path->taken[C3]==0) //Jump condition M->C3
- {
- addToPath(current_path, C3);
- pathfinder(current_path, depth+1);
- }
- // there is no way possible, STOP (In fact we can take into account the jump)
- //drawpattern(current_path);
- //printf("No possible from C2\n");
- //drawpattern(current_path);
- current_path->path[current_path->index] = 0;
- current_path->index--;
- updateTakenMap(current_path);
- return;
- //END OF C2 CASE
- }
- if(init==C3){
- if(current_path->taken[E2]==0) //If E1 is not taken
- {
- addToPath(current_path, E2);
- pathfinder(current_path, depth+1);
- }
- if (current_path->taken[E4]==0) // E1 is taken so we check if E3 is taken
- {
- addToPath(current_path, E4);
- pathfinder(current_path, depth+1);
- }
- if (current_path->taken[E3]==0)
- {
- addToPath(current_path, E3);
- pathfinder(current_path, depth+1);
- }
- if (current_path->taken[E1]==0)
- {
- addToPath(current_path, E1);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[M]==0)
- {
- addToPath(current_path, M);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[E1]==1 && current_path->taken[C1]==0) //Jump condition
- {
- addToPath(current_path, C1);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[E3]==1 && current_path->taken[C4]==0) //Jump condition
- {
- addToPath(current_path, C4);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[M]==1 && current_path->taken[C2]==0) //Jump condition M->C2
- {
- addToPath(current_path, C2);
- pathfinder(current_path, depth+1);
- }
- // there is no way possible, STOP (In fact we can take into account the jump)
- //printf("No possible from C3\n");
- current_path->path[current_path->index] = 0;
- current_path->index--;
- updateTakenMap(current_path);
- return;
- }
- if(init==C4){
- if(current_path->taken[E3]==0) //Classic
- {
- addToPath(current_path, E3);
- pathfinder(current_path, depth+1);
- }
- if (current_path->taken[E4]==0) //Classic
- {
- addToPath(current_path, E4);
- pathfinder(current_path, depth+1);
- }
- if (current_path->taken[E1]==0) //Long
- {
- addToPath(current_path, E1);
- pathfinder(current_path, depth+1);
- }
- if (current_path->taken[E2]==0) //Long
- {
- addToPath(current_path, E2);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[M]==0)
- {
- addToPath(current_path, M);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[E1]==1 && current_path->taken[C1]==0) //Jump condition
- {
- addToPath(current_path, C1);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[E3]==1 && current_path->taken[C4]==0) //Jump condition
- {
- addToPath(current_path, C4);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[M]==1 && current_path->taken[C1]==0) //Jump condition M->C1
- {
- addToPath(current_path, C1);
- pathfinder(current_path, depth+1);
- }
- // there is no way possible, STOP (In fact we can take into account the jump)
- //printf("No possible from C4\n");
- //drawpattern(current_path);
- current_path->path[current_path->index] = 0;
- current_path->index--;
- updateTakenMap(current_path);
- return;
- }
- //----------------------------------------------------
- //END OF CORNER CASES
- //------------------------------------------------------
- if(init==E1){
- if(current_path->taken[C1]==0) //Corner
- {
- addToPath(current_path, C1);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[C2]==0)//Corner
- {
- addToPath(current_path, C2);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[E2]==0)//Edge
- {
- addToPath(current_path, E2);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[E3]==0)//Edge
- {
- addToPath(current_path, E3);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[M]==0)//Middle
- {
- addToPath(current_path, M);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[M]==1 && current_path->taken[E4]==0)//Jump over middle
- {
- addToPath(current_path, E4);
- pathfinder(current_path, depth+1);
- }
- //NO PATH
- //printf("No possible from E1\n");
- //drawpattern(current_path);
- current_path->path[current_path->index] = 0;
- current_path->index--;
- updateTakenMap(current_path);
- return;
- }
- if(init==E2){
- if(current_path->taken[C1]==0) //Corner
- {
- addToPath(current_path, C1);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[C3]==0)//Corner
- {
- addToPath(current_path, C3);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[E1]==0)//Edge
- {
- addToPath(current_path, E1);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[E4]==0)//Edge
- {
- addToPath(current_path, E4);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[M]==0)//Middle
- {
- addToPath(current_path, M);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[M]==1 && current_path->taken[E3]==0)//Jump over middle
- {
- addToPath(current_path, E3);
- pathfinder(current_path, depth+1);
- }
- //NO PATH
- //printf("No possible from E2\n");
- //drawpattern(current_path);
- current_path->path[current_path->index] = 0;
- current_path->index--;
- updateTakenMap(current_path);
- }
- if(init==E3){
- if(current_path->taken[C2]==0) //Corner
- {
- addToPath(current_path, C2);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[C4]==0)//Corner
- {
- addToPath(current_path, C4);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[E1]==0)//Edge
- {
- addToPath(current_path, E1);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[E4]==0)//Edge
- {
- addToPath(current_path, E4);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[M]==0)//Middle
- {
- addToPath(current_path, M);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[M]==1 && current_path->taken[E2]==0)//Jump over middle
- {
- addToPath(current_path, E2);
- pathfinder(current_path, depth+1);
- }
- //NO PATH
- //printf("No possible from E3\n");
- //drawpattern(current_path);
- current_path->path[current_path->index] = 0;
- current_path->index--;
- updateTakenMap(current_path);
- return;
- }
- if(init==E4){
- if(current_path->taken[C3]==0) //Corner
- {
- addToPath(current_path, C3);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[C4]==0)//Corner
- {
- addToPath(current_path, C4);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[E2]==0)//Edge
- {
- addToPath(current_path, E2);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[E3]==0)//Edge
- {
- addToPath(current_path, E3);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[M]==0)//Middle
- {
- addToPath(current_path, M);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[M]==1 && current_path->taken[E1]==0)//Jump over middle
- {
- addToPath(current_path, E1);
- pathfinder(current_path, depth+1);
- }
- //NO PATH
- //printf("No possible from E4\n");
- //drawpattern(current_path);
- current_path->path[current_path->index] = 0;
- current_path->index--;
- updateTakenMap(current_path);
- return;
- }
- //----------------------------------------------------
- //END OF EDGE CASES
- //------------------------------------------------------
- if(init==M){
- if(current_path->taken[E1]==0) //If E1 is not taken
- {
- addToPath(current_path, E1);
- pathfinder(current_path, depth+1);
- }
- if (current_path->taken[E2]==0) // E1 is taken so we check if E2 is taken
- {
- addToPath(current_path, E2);
- pathfinder(current_path, depth+1);
- }
- if (current_path->taken[E3]==0) // E2 is taken so we check if E3 is taken
- {
- addToPath(current_path, E3);
- pathfinder(current_path, depth+1);
- }
- if (current_path->taken[E4]==0) // E2 is taken so we check if E3 is taken
- {
- addToPath(current_path, E4);
- pathfinder(current_path, depth+1);
- }
- if(current_path->taken[C1]==0) //If E1 is not taken
- {
- addToPath(current_path, C1);
- pathfinder(current_path, depth+1);
- }
- if (current_path->taken[C2]==0) // E1 is taken so we check if E2 is taken
- {
- addToPath(current_path, C2);
- pathfinder(current_path, depth+1);
- }
- if (current_path->taken[C3]==0) // E2 is taken so we check if E3 is taken
- {
- addToPath(current_path, C3);
- pathfinder(current_path, depth+1);
- }
- if (current_path->taken[C4]==0) // E2 is taken so we check if E3 is taken
- {
- addToPath(current_path, C4);
- pathfinder(current_path, depth+1);
- }
- //NO PATH
- //printf("No possible from M\n");
- //drawpattern(current_path);
- current_path->path[current_path->index] = 0;
- current_path->index--;
- updateTakenMap(current_path);
- return;
- }
- //pathfinder(current_path, depth+1);
- }
- void addToPath(t_path* p, char toAdd){
- if(toAdd<1 || toAdd>9){
- printf("Error: addToPath Function cannot take this parameter: toAdd =%d\n", toAdd);
- exit(-1);
- }
- else{
- if(p->taken[toAdd]==1){
- printf("Bug: not possible to add a taken to path...\n");
- exit(-1);
- }
- else{
- p->index++; //Add a step to the path
- p->path[p->index] = toAdd; //Add toAdd to current path
- updateTakenMap(p);
- }
- }
- }
- void drawpattern(t_path* p){
- int i;
- for(i=0; i<p->index+1; i++){
- switch(p->path[i]){
- case E1:
- printf("->E1");
- break;
- case E2:
- printf("->E2");
- break;
- case E3:
- printf("->E3");
- break;
- case E4:
- printf("->E4");
- break;
- case C1:
- printf("->C1");
- break;
- case C2:
- printf("->C2");
- break;
- case C3:
- printf("->C3");
- break;
- case C4:
- printf("->C4");
- break;
- case M:
- printf("->M");
- break;
- default :
- printf("default");
- }
- }
- printf("\n");
- }
- void moveCursor(int row, int col){
- printf("\033[2J");
- printf("\033[%d;%dH", row, col);
- printf("Coucou\n");
- }
- t_path* copyTPath(t_path* toCopy){
- t_path* toReturn = NULL;
- char p[DEPTH];
- char tak[9];
- int index;
- int i;
- toReturn = (t_path*)malloc(sizeof(t_path));
- for (i = 0; i < toCopy->index; ++i)
- {
- toReturn->path[i] = toCopy->path[i];
- }
- for (i = 1; i <=9; ++i)
- {
- toReturn->taken[i] = toCopy->taken[i];
- }
- toReturn->index = toCopy->index;
- return toReturn;
- }
- void drawTakenMap(t_path* p){
- int i;
- printf("taken:");
- for (i = 1; i <= 9; ++i)
- {
- if(p->taken[i] == 1){
- switch(i){
- case E1:
- printf(" E1 ");
- break;
- case E2:
- printf(" E2 ");
- break;
- case E3:
- printf(" E3 ");
- break;
- case E4:
- printf(" E4 ");
- break;
- case C1:
- printf(" C1 ");
- break;
- case C2:
- printf(" C2 ");
- break;
- case C3:
- printf(" C3 ");
- break;
- case C4:
- printf(" C4 ");
- break;
- case M:
- printf(" M ");
- break;
- default :
- printf("default : %d", i);
- }
- }
- }
- printf("\n");
- }
- void updateTakenMap(t_path* p){
- int i = 0;
- //reset taken
- for(i = 1; i<=9; i++){
- p->taken[i] = 0;
- }
- for(i = 0; i<=p->index; i++){
- p->taken[p->path[i]] = 1;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement