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

핫 AI 도구

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

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

Undress AI Tool
무료로 이미지를 벗다

Clothoff.io
AI 옷 제거제

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

인기 기사

뜨거운 도구

메모장++7.3.1
사용하기 쉬운 무료 코드 편집기

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

스튜디오 13.0.1 보내기
강력한 PHP 통합 개발 환경

드림위버 CS6
시각적 웹 개발 도구

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

뜨거운 주제











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

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

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

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

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

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

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

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