목차
설명
백엔드 개발 C++ 미로 속의 쥐를 위한 C 프로그램 - 역추적-2

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

Sep 11, 2023 pm 02:25 PM

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

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

迷宫中老鼠的C程序 - 回溯法-2

이것이 해결책입니다.

迷宫中老鼠的C程序 - 回溯法-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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

AI Hentai Generator

AI Hentai Generator

AI Hentai를 무료로 생성하십시오.

뜨거운 도구

메모장++7.3.1

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전

SublimeText3 중국어 버전

중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

신 수준의 코드 편집 소프트웨어(SublimeText3)

C 언어 함수에 의해 반환 된 값 유형은 무엇입니까? 반환 값을 결정하는 것은 무엇입니까? C 언어 함수에 의해 반환 된 값 유형은 무엇입니까? 반환 값을 결정하는 것은 무엇입니까? Mar 03, 2025 pm 05:52 PM

이 기사는 기본 (int, float, char 등), 파생 (배열, 포인터, 스트러크) 및 공극 유형을 포함하는 C 함수 리턴 유형에 대해 자세히 설명합니다. 컴파일러는 함수 선언과 반환 명령문을 통해 반환 유형을 결정합니다.

Gulc : C 도서관은 처음부터 구축되었습니다 Gulc : C 도서관은 처음부터 구축되었습니다 Mar 03, 2025 pm 05:46 PM

GULC는 최소 오버 헤드, 공격적인 인라인 및 컴파일러 최적화 우선 순위를 정하는 고성능 C 라이브러리입니다. 고주파 거래 및 임베디드 시스템과 같은 성능 크리티컬 애플리케이션에 이상적 인 디자인은 단순성, 모듈을 강조합니다.

C 언어 기능의 정의 및 호출 규칙은 무엇이며 C 언어 기능의 정의 및 호출 규칙은 무엇이며 Mar 03, 2025 pm 05:53 PM

이 기사는 C 함수 선언 대 정의, 인수 통과 (값 및 포인터 별), 리턴 값 및 메모리 누출 및 유형 불일치와 같은 일반적인 함정을 설명합니다. 모듈성 및 Provi에 대한 선언의 중요성을 강조합니다.

C 언어 함수 형식 문자 케이스 변환 단계 C 언어 함수 형식 문자 케이스 변환 단계 Mar 03, 2025 pm 05:53 PM

이 기사는 문자열 케이스 변환에 대한 C 기능을 자세히 설명합니다. ctype.h의 toupper () 및 tolower ()를 사용하고 문자열을 통한 반복 및 널 터미네이터를 처리합니다. ctype.h를 잊어 버리고 문자 그럴을 수정하는 것과 같은 일반적인 함정은 다음과 같습니다.

메모리에 저장된 C 언어 함수의 반환 값은 어디에 있습니까? 메모리에 저장된 C 언어 함수의 반환 값은 어디에 있습니까? Mar 03, 2025 pm 05:51 PM

이 기사에서는 C 기능 반환 값 저장을 검사합니다. 작은 반환 값은 일반적으로 속도 레지스터에 저장됩니다. 더 큰 값은 포인터에 메모리 (스택 또는 힙)를 사용하여 수명에 영향을 미치고 수동 메모리 관리가 필요할 수 있습니다. 직접 ACC

뚜렷한 사용 및 문구 공유 뚜렷한 사용 및 문구 공유 Mar 03, 2025 pm 05:51 PM

이 기사는 형용사 "별개", 문법 기능, 공통 문구 (예 : "구별", "뚜렷하게 다른") 및 공식 대 비공식의 미묘한 응용 프로그램의 다각적 인 사용을 분석합니다.

STL (정렬, 찾기, 변환 등)의 알고리즘을 효율적으로 사용하려면 어떻게합니까? STL (정렬, 찾기, 변환 등)의 알고리즘을 효율적으로 사용하려면 어떻게합니까? Mar 12, 2025 pm 04:52 PM

이 기사는 효율적인 STL 알고리즘 사용을 자세히 설명합니다. 데이터 구조 선택 (벡터 대 목록), 알고리즘 복잡성 분석 (예 : std :: sort vs. std :: partial_sort), 반복자 사용 및 병렬 실행을 강조합니다. 일반적인 함정과 같은

C 표준 템플릿 라이브러리 (STL)는 어떻게 작동합니까? C 표준 템플릿 라이브러리 (STL)는 어떻게 작동합니까? Mar 12, 2025 pm 04:50 PM

이 기사에서는 컨테이너, 반복자, 알고리즘 및 함수 인 핵심 구성 요소에 중점을 둔 C 표준 템플릿 라이브러리 (STL)에 대해 설명합니다. 일반적인 프로그래밍을 가능하게하기 위해 이러한 상호 작용, 코드 효율성 및 가독성 개선 방법에 대해 자세히 설명합니다.

See all articles