장애물이 -1로 표시되고 투명 셀이 -1이 아닌 값을 갖는 행 X 열 행렬로 표현되는 미로가 주어집니다. 목표는 첫 번째 셀 arr[0][0]에서 시작하여 두 번의 이동만 허용되도록 마지막 셀 arr[row][col]에 도달하는 것입니다.
- arr[i][j]를 arr[i][j+1]로 오른쪽 이동하고
- arr[i][j]를 arr[i+1][j]로 아래로 이동합니다.
예를 들어 이해합시다.
입력 - arr[행][열] ={{0, 0, 0}, {-1, -1, 0}, {0, 0, 0}}
출력 - 미로에서 목적지에 도달하는 방법의 수는 다음과 같습니다. 1
설명
0 1 2
0 0 0 0
1 -1 -1 0
2 0 0 0
방법은 다음과 같습니다.
- 셀(0,0) → 셀(0,1) → 셀(0,2) → 셀(1,2) → 셀(2,0)
입력 - arr[행][열] ={ {0, 0, 0, 0}, {-1, 0, -1, 0}, {-1, 0, -1, 0}, {0, 0, 0, 0}}
출력 - 미로에서 목적지에 도달하는 방법의 수는 다음과 같습니다. 2
설명
0 1 2 3
0 0 0 0 0
1 -1 0 -1 0
2 -1 0 -1 0
3 0 0 0 0
방법은 다음과 같습니다.
- 셀(0,0) → 셀(0,1) → 셀(1,1) → 셀(2,1) → 셀(3,1) → 셀(3,2) → 셀(3,3) )
- 셀(0,0) → 셀(0,1) → 셀(0,2) → 셀(0,3) → 셀(1,3) → 셀(2,3) → 셀(3,3) )
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
이 접근 방식에서는 먼저 모든 0을 1로 설정합니다. 각 셀에 대해 다시 미로 행렬을 탐색하고 차단(-1)이면 무시합니다. 그렇지 않은 경우 위쪽 셀(i-1,j)과 왼쪽 셀(i,j-1)을 확인합니다. 0보다 크면 현재 셀(i,j)에 값을 추가합니다. 이런 식으로 셀(row-1,col-1)에서 합계를 도달하는 총 방법으로 얻습니다.
- 입력 배열 arr[row][col]을 Maze로 사용합니다.
- destination_maze(int arr[row][col]) 함수는 arr을 받아 미로에서 목적지에 도달하는 방법의 수를 반환합니다.
- 첫 번째 셀이 차단되면 끝까지 도달하는 방법으로 0을 반환합니다.
- 이제 가장 왼쪽 열을 탐색하고 모든 0을 1로 설정합니다. 처음에는 차단으로 인해 루프 아래에 있는 셀에 도달할 수 없으므로 루프가 중단됩니다. 인덱스 i=0에서 i
- j=0에서 j
- 셀(1,1)에서 arr을 다시 탐색하고 arr[i][j]가 -1이면 아무 것도 하지 않습니다.
- arr[i-1][j] 또는 arr[i][j-1]이 0보다 크면 arr[i][j]에 도달할 수 있습니다. 가치를 더하세요.
- 마지막에 도달하는 전체 방법으로 arr[row-1][col-1]이 있습니다.
- 0보다 크면 반환하고 그렇지 않으면 0을 반환합니다.
- j=0에서 j
예시
#include<bits/stdc++.h>
using namespace std;
#define row 3
#define col 3
int destination_maze(int arr[row][col]) {
if (arr[0][0] == -1) {
return 0;
}
for (int i = 0; i < row; i++) {
if (arr[i][0] == 0) {
arr[i][0] = 1;
} else {
break;
}
}
for (int i = 1; i < col; i++) {
if (arr[0][i] == 0) {
arr[0][i] = 1;
} else {
break;
}
}
for (int i = 1; i < row; i++) {
for (int j = 1; j < col; j++) {
if (arr[i][j] == -1) {
continue;
}
if (arr[i - 1][j] > 0) {
arr[i][j] = (arr[i][j] + arr[i - 1][j]);
}
if (arr[i][j - 1] > 0) {
arr[i][j] = (arr[i][j] + arr[i][j - 1]);
}
}
}
if (arr[row - 1][col - 1] > 0) {
return arr[row - 1][col - 1];
} else {
return 0;
}
}
int main() {
int arr[row][col] = {
{
0,
0,
0
},
{
-1,
-1,
0
},
{
0,
0,
0
}
};
cout << "Count of number of ways to reach destination in a Maze are: " << destination_maze(arr);
return 0;
} 위의 코드를 실행하면 다음 출력이 생성됩니다 -
출력
Count of number of ways to reach destination in a Maze are: 1