미로 문제의 쥐

이 문제에는 N x N 크기의 주어진 미로가 있습니다. 소스와 대상 위치는 각각 왼쪽 상단 셀과 오른쪽 하단 셀입니다. 일부 셀은 이동이 가능하고 일부 셀은 차단됩니다. 한 쥐가 시작 정점에서 대상 정점으로 이동하기 시작하면 경로를 완료할 수 있는 방법이 있는지 찾아야 합니다. 가능하면 쥐의 올바른 경로를 표시합니다.

미로는 이진 행렬을 사용하여 제공되며 1로 표시되고 유효한 경로이며 그렇지 않으면 차단된 셀에 대해 0으로 표시됩니다.

참고: 쥐는 오른쪽 또는 아래쪽의 두 방향으로만 이동할 수 있습니다.

입력 및 출력

입력:이 알고리즘은 미로를 행렬로 사용합니다. 행렬에서 값 1은 여유 공간을 나타내고 0은 벽 또는 차단된 영역을 나타냅니다. 이 다이어그램에서 왼쪽 위의 원은 시작점을 나타내고 오른쪽 아래의 원은 끝점을 나타냅니다. .출력:행렬을 표시합니다. 그 행렬에서 우리는 목적지에 도달하는 쥐의 경로를 찾을 수 있습니다. 

알고리즘

유효함(x, y)

입력: 미로의 x 및 y 지점입니다.

출력: (x,y) 자리가 유효하면 참, 그렇지 않으면 거짓입니다.

x와 y가 범위 내에 있고 (x,y) 자리가 차단되지 않은 경우 시작하면 true를 반환합니다. return falseEnd

RatMaze(x, y) 해결

입력 - 시작점 x와 y.

출력 − 목적지에 도달하기 위해 쥐가 따라야 하는 경로, 그렇지 않으면 false입니다.

(x,y)가 오른쪽 하단 모서리인 경우 시작하고, isValidPlace(x, y) =true인 경우 true를 반환하고, solveRatMaze(x+1)인 경우 (x, y) 장소를 1로 표시합니다. , y) =true, then //정방향 이동의 경우 true 반환 solveRatMaze(x, y+1) =true, then //아래쪽 이동의 경우 true 반환 백트랙이 false를 반환할 때 (x,y)를 0으로 표시 return falseEnd 
예시
 
#include#define N 5 namespace std;int maze[N][N] ={ {1, 0, 0, 0, 0}, {1, 1, 0, 1, 0}, { 0, 1, 1, 1, 0}, {0, 0, 0, 1, 0}, {1, 1, 1, 1, 1}};int sol[N][N]; //미로 경로의 최종 솔루션은 여기에 저장됩니다. showPath() { for (int i =0; i =0 &&x =0 &&y  
출력
 
1 0 0 0 01 1 0 0 00 1 1 1 00 0 0 1 00 0 0 1 1