포인터 C에서 이진 트리 미로 해답

Question

로봇 시뮬레이터를 C로 프로그래밍해야합니다. 로봇은 재귀 Backtracker 알고리즘을 사용하여 2 차원 labirinth의 Exit를 찾아야합니다.이 알고리즘은 어떻게 작동 하나 이해하지 못합니다. 그것을 구현하는 방법을 알아라. 포인터를 사용하여 이진 트리를 사용할 수 있다고 생각하지만 어떻게해야할지 모르겠다. 나에게 설명해 주시겠습니까?

이

내가 이제 로봇이 때문에 나는 이진 트리가 유용 할 것이다 방법을 이해하는 힘든 시간을 보내고있어 방향을

#ifdef __unix__ 
#include <unistd.h> 
#elif defined _WIN32 
#include <windows.h> 
#define sleep(x) Sleep(1000 * x) 
#endif 

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

void goUp(); 
void goDown(); 
void goLeft(); 
void goRight(); 

typedef struct robot { 
    int direction; 
    bool is_moving; 
}robot; 

typedef struct room { 
    robot robot; 
    bool is_robot; 
    int obstacle; 

}room; 

room Room[20][20]; 
int r = 12; 
int c = 10; 

void generation(room matrix[20][20]) 
{ 
    srand(time(NULL)); 
    int x,i,j; 
    x=0; 
    for(i=0;i<20;i++) 
    { 
     for(j=0;j<20;j++) 
     { 
      matrix[i][j].is_robot=false; 
      x=rand()%100+1; 
      if(x==1||x==50||x==100) 
      { 
       matrix[i][j].obstacle=1; 
      } 
      else 
      { 
       matrix[i][j].obstacle=0; 
      } 
     } 
    } 
} 

void print_matrix(room matrix[20][20]) 
{ 
    int i,j; 

    for(i=0;i<20;i++) 
    { 
     for(j=0;j<20;j++) 
     { 
      if(matrix[i][j].obstacle==0) 
      { 
       if(matrix[i][j].is_robot==true) 
       { 
        printf("I"); 
       } 
       else 
       { 
        printf(" "); 
       } 
      } 
      else 
      { 
       if(matrix[i][j].is_robot==true) 
       { 
        printf("I"); 
       } 
       else 
       { 
        printf("o"); 
       } 
      } 
     } 
     printf("\n"); 
    } 
} 

bool changeDirection(room Room[20][20],int i,int j) 
{ 
    if(Room[i][j].robot.direction == 1) 
    { 
     if(Room[i-1][j].obstacle == 1 || i-1 == 0) 
     { 
      if(Room[i+1][j].obstacle == 1 || i+1 == 19) 
      { 
       Room[i][j].robot.direction = 2; 
       return true; 
      } 
      else 
      { 
       Room[i][j].robot.direction = 4; 
       return true; 
      } 

     } 
     else 
     { 
      Room[i][j].robot.direction = 3; 
      return true; 
     } 
    } 



    if(Room[i][j].robot.direction == 2) 
    { 
     if(Room[i-1][j].obstacle == 1 || i-1 == 0) 
     { 
      if(Room[i+1][j].obstacle == 1 || i+1 == 19) 
      { 
       Room[i][j].robot.direction = 1; 
       return true; 
      } 
      else 
      { 
       Room[i][j].robot.direction = 4; 
       return true; 
      } 

     } 
     else 
     { 
      Room[i][j].robot.direction = 3; 
      return true; 
     } 
    } 


    if(Room[i][j].robot.direction == 3) 
    { 
     if(Room[i][j+1].obstacle == 1 || j+1 == 19) 
     { 
      if(Room[i][j-1].obstacle == 1 || j-1 == 0) 
      { 
       Room[i][j].robot.direction = 4; 
       return true; 
      } 
      else 
      { 
       Room[i][j].robot.direction = 2; 
       return true; 
      } 

     } 
     else 
     { 
      Room[i][j].robot.direction = 1; 
      return true; 
     } 
    } 

    if(Room[i][j].robot.direction == 4) 
    { 
     if(Room[i][j+1].obstacle == 1 || j+1 == 19) 
     { 
      if(Room[i][j-1].obstacle == 1 || j-1 == 0) 
      { 
       Room[i][j].robot.direction = 3; 
       return true; 
      } 
      else 
      { 
       Room[i][j].robot.direction = 2; 
       return true; 
      } 

     } 
     else 
     { 
      Room[i][j].robot.direction = 1; 
      return true; 
     } 
    } 
} 

void goRight() 
{ 
    c=c+1; 
    Room[r][c].robot.direction=1; 
    Room[r][c].is_robot=true; 
    Room[r][c-1].is_robot=false; 
} 

void goLeft() 
{ 
    c=c-1; 
    Room[r][c].robot.direction=2; 
    Room[r][c].is_robot=true; 
    Room[r][c+1].is_robot=false; 
} 

void goUp() 
{ 
    r=r-1; 
    Room[r][c].robot.direction=3; 
    Room[r][c].is_robot=true; 
    Room[r+1][c].is_robot=false; 
} 
void goDown() 
{ 
    r=r+1; 
    Room[r][c].robot.direction=4; 
    Room[r][c].is_robot=true; 
    Room[r-1][c].is_robot=false; 
} 

int main() 
{ 

    generation(Room); 
    Room[r][c].robot.direction = 1; 
    Room[r][c].robot.is_moving = true; 
    Room[r][c].is_robot = true; 

    do 
    { 
     Room[r][c].robot.is_moving = true; 
     if (Room[r][c].robot.direction == 1 && Room[r][c].robot.is_moving == true) // destra 
     { 
      if(Room[r][c +1].obstacle == 1 || c+1 == 19) 
      { 

       changeDirection(Room,r,c); 
      } 
      else 
      { 
       goRight(); 
      } 
     } 

     if (Room[r][c].robot.direction == 2 && Room[r][c].robot.is_moving == true) // sinistra 
     { 
      if(Room[r][c -1].obstacle == 1 || c-1 == 0) 
      { 
       changeDirection(Room,r,c); 
      } 
      else 
      { 
       goLeft(); 
      } 
     } 

     if (Room[r][c].robot.direction == 3 && Room[r][c].robot.is_moving == true) // su 
     { 
      if(Room[r-1][c].obstacle == 1 || r-1 == 0) 
      { 
       changeDirection(Room,r,c); 
      } 
      else 
      { 
       goUp(); 
      } 
     } 

     if (Room[r][c].robot.direction == 4 && Room[r][c].robot.is_moving == true) // giu 
     { 
      if(Room[r+1][c].obstacle == 1 || r+1 == 19) 
      { 
       changeDirection(Room,r,c); 
      } 
      else 
      { 
       goDown(); 
      } 
     } 

     print_matrix(Room); 
     sleep(0.1); 
     system("cls"); 

    } 
    while(1); 
    print_matrix(Room); 
} 

Answer 1

을 변경하는 방법의 루프에 진입, 만든 프로그램입니다 미로에서 길을 찾는 것 (어쩌면 미로를 나타 내기 위해 사용되는 것일까?)하지만 나는 아마도 눈이 멀었다. 나는 단순히 2d int 배열을 만들었고 0은 위치가 차단되었다는 것을 의미하고 (벽이 있거나 뭔가가 있음) 그리고 1은 열려 있다는 것을 의미한다 (거기로 이동할 수 있음). 무력의 철수 절차는 (위, 아래, 왼쪽, 오른쪽) 직교 운동을가는 것입니다 : 내가 가지고있는 위의 아이디어를 사용

"+" is where you start ([1][1]) 
"-" is your destination ([3][1]) 
"#" is a blocked region 

=========== 
|#|#|#|#|#| 
|#|+| |#|#| 
|#|#| |#|#| 
|#|-| | |#| 
|#|#|#|#|#| 
=========== 

:

f(x,y){ 
    // you found the place your want to go to 
    if (x,y) is (destinationX,destinationY) 
     return true 

    block the position (x,y) // i.e. mark current position as visited 

    if there is an open spot at (x,y-1) AND f(x,y-1) 
     return true 
    if there is an open spot at (x,y+1) AND f(x,y+1) 
     return true 
    if there is an open spot at (x-1,y) AND f(x-1,y) 
     return true 
    if there is an open spot at (x+1,y) AND f(x+1,y) 
     return true 

    return false 
} 

당신처럼 보이는 미로 있다고 가정 :

#include <stdio.h> 
#define width 5 
#define height 5 

// print maze 
void print(char arr[][width]){ 
    for (int i = 0; i < 2*width+1; i++) printf("="); 
    printf("\n"); 
    for (int i = 0; i < height; i++) { 
     for (int j = 0; j < width; j++) { 
      printf("|%c",arr[i][j]); 
     } 
     printf("|\n"); 
    } 
    for (int i = 0; i < 2*width+1; i++) printf("="); 
} 


// starting from (x,y) to (destX,destY) 
int path(int arr[][width],int x,int y,int destX,int destY,char toDest[][width]){ 
    if (x==destX && y==destY) { 
     toDest[y][x] = '*'; 
     print(toDest); 
     return 1; 
    } 
    // mark current position as visited 
    arr[y][x] = 0; 
    toDest[y][x] = '*'; 

    // left 
    if (arr[y][x-1] && path(arr,x-1,y,destX,destY,toDest)) 
     return 1; 

    // right 
    if (arr[y][x+1] && path(arr,x+1,y,destX,destY,toDest)) 
     return 1; 

    // up 
    if (arr[y-1][x] && path(arr,x,y-1,destX,destY,toDest)) 
     return 1; 

    // down 
    if (arr[y+1][x] && path(arr,x,y+1,destX,destY,toDest)) 
     return 1; 

    return 0; 
} 


int main() { 
    // use this to store path 
    // and then print it out if found 
    char toDest[height][width] = { 
      {'#','#','#','#','#'}, 
      {'#',' ',' ','#','#'}, 
      {'#','#',' ','#','#'}, 
      {'#',' ',' ',' ','#'}, 
      {'#','#','#','#','#'} 
    }; 

    // 0 -> position is blocked 
    // 1 -> position is open 
    int maze[height][width] = { 
      {0,0,0,0,0}, 
      {0,1,1,0,0}, 
      {0,0,1,0,0}, 
      {0,1,1,1,0}, 
      {0,0,0,0,0} 
    }; 

    path(maze,1,1,1,3,toDest); 
} 

출력 :

=========== 
|#|#|#|#|#| 
|#|*|*|#|#| 
|#|#|*|#|#| 
|#|*|*| |#| 
|#|#|#|#|#| 
=========== 

출력에서 ​​경로는 *으로 지정됩니다.