미로 속의 쥐를 위한 C 프로그램 - 역추적-2

미로 속의 쥐도 역추적을 활용하는 일반적인 문제입니다. I

미로는 일부 세포가 막혀 있는 2차원 매트릭스입니다. 셀 중 하나가 소스 셀이고 거기서부터 시작해야 합니다. 또 하나는 목적지, 우리가 가야 할 곳입니다. 차단된 셀에 들어가지 않고 소스에서 대상까지의 경로를 찾아야 합니다. 풀리지 않은 미로의 사진은 아래와 같습니다.

이것이 해결책입니다.

이 퍼즐을 풀려면 먼저 소스 유닛에서 시작하여 경로가 막히지 않는 방향으로 이동합니다. 선택한 길이 우리를 목적지로 인도한다면 퍼즐은 해결됩니다. 그렇지 않으면 우리는 돌아와서 우리가 가고 있는 길의 방향을 바꿀 것입니다. 코드에서도 동일한 논리를 구현하겠습니다.

Input:
maze[][] = {
{0,1,0,1,1},
{0,0,0,0,0},
{1,0,1,0,1},
{0,0,1,0,0},
{1,0,0,1,0}}

Output:
1 0 0 0 0
1 1 1 1 0
0 0 0 1 0
0 0 0 1 1
0 0 0 0 1

설명

먼저 미로를 표현하기 위한 행렬을 만들겠습니다. 행렬의 요소는 0 또는 1이 됩니다. 1은 막힌 세포를 의미하고 0은 움직일 수 있는 세포를 의미합니다. 위에 표시된 미로의 행렬은 다음과 같습니다.

0 1 0 1 1
0 0 0 0 0
1 0 1 0 1
0 0 1 0 0
1 0 0 1 0

이제 해를 저장하기 위해 동일한 차원의 또 다른 행렬을 만듭니다. 해당 요소도 0 또는 1이 됩니다. 1은 경로의 셀을 나타내고 나머지 셀은 0이 됩니다. 솔루션을 나타내는 행렬은 다음과 같습니다.

1 0 0 0 0
1 1 1 1 0
0 0 0 1 0
0 0 0 1 1
0 0 0 0 1

이제 행렬이 생겼습니다. 다음으로, 시작 셀에서 대상 셀까지의 경로를 찾을 것이며, 우리가 취할 단계는 다음과 같습니다:

• 현재 셀을 확인하고, 대상 셀이면 퍼즐이 해결됩니다.

• 그렇지 않다면 아래로 이동하여 다음 셀로 이동할 수 있는지 확인하세요. (셀로 이동하려면 해당 셀이 비어 있어야 하며 경로에 없어야 합니다.)

• 다음 셀로 이동할 수 있으면 다음 아래쪽 셀로 가는 길을 따라 계속 이동하세요.

• 그렇지 않다면 오른쪽으로 이동해보세요. 오른쪽이 막혀 있거나 점유되어 있으면 위로 이동하세요.

• 마찬가지로 위로 이동이 불가능할 경우에는 간단히 왼쪽 셀로 이동하겠습니다.

• 네 방향(아래, 오른쪽, 위, 왼쪽) 중 어느 방향으로도 이동할 수 없는 경우 간단히 돌아가서 현재 경로를 변경하세요(역추적).

그래서 요약하자면 현재 셀에서 다른 셀(아래, 오른쪽, 위, 왼쪽)로 이동을 시도하고 이동이 불가능하면 돌아가서 경로 방향을 다른 셀 그리드로 변경합니다.

printsolution → 이 함수는 솔루션 매트릭스를 인쇄합니다.

solvemaze → 실제로 역추적 알고리즘을 구현하는 함수입니다. 먼저 우리 셀이 대상 셀인지 확인합니다. 그렇다면 (r==SIZE-1) 및 (c==SIZE-1)입니다. 타겟 셀이라면 퍼즐이 해결된 것입니다. 그렇지 않은 경우 유효한 모바일 셀인지 확인합니다. 유효한 셀은 행렬에 있어야 합니다. 즉, 인덱스는 0과 SIZE-1 사이여야 하고, r>=0 && c>=0 && r

예

#include <iostream>
using namespace std;
#define SIZE 5
//the maze problem
int maze[SIZE][SIZE] = {
   {0,1,0,1,1},
   {0,0,0,0,0},
   {1,0,1,0,1},
   {0,0,1,0,0},
   {1,0,0,1,0}
};
//matrix to store the solution
int solution[SIZE][SIZE];
//function to print the solution matrix
void printsolution() {
   int i,j;
   for(i=0;i<SIZE;i++) {
      for(j=0;j<SIZE;j++) {
         printf("%d\t",solution[i][j]);
      }
      printf("</p><p></p><p>");
   }
}
//function to solve the maze
//using backtracking
int solvemaze(int r, int c) {
   //if destination is reached, maze is solved
   //destination is the last cell(maze[SIZE-1][SIZE-1])
   if((r==SIZE-1) && (c==SIZE-1) {
      solution[r][c] = 1;
      return 1;
   }
   //checking if we can visit in this cell or not
   //the indices of the cell must be in (0,SIZE-1)
   //and solution[r][c] == 0 is making sure that the cell is not already visited
   //maze[r][c] == 0 is making sure that the cell is not blocked
   if(r>=0 && c>=0 && r<SIZE && c<SIZE && solution[r][c] == 0 && maze[r][c] == 0){
      //if safe to visit then visit the cell
      solution[r][c] = 1;
      //going down
      if(solvemaze(r+1, c))
         return 1;
      //going right
      if(solvemaze(r, c+1))
         return 1;
      //going up
      if(solvemaze(r-1, c))
         return 1;
      //going left
      if(solvemaze(r, c-1))
         return 1;
      //backtracking
      solution[r][c] = 0;
      return 0;
   }
   return 0;
}
int main() {
   //making all elements of the solution matrix 0
   int i,j;
   for(i=0; i<SIZE; i++) {
      for(j=0; j<SIZE; j++) {
         solution[i][j] = 0;
      }
   }
   if (solvemaze(0,0))
      printsolution();
   else
      printf("No solution</p><p>");
   return 0;
}

위 내용은 미로 속의 쥐를 위한 C 프로그램 - 역추적-2의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!