음수가 아닌 숫자를 요소로 포함하는 정방형 행렬[][]이 주어집니다. 또한 가변 점수가 주어집니다. 목표는 허용되는 이동만 오른쪽 이동과 아래쪽 이동이 되도록 matrix[][]에서 요소를 추가하여 주어진 점수에 도달하는 방법을 계산하는 것입니다.
행렬[0][0]에서 시작하여 행렬[0][1](오른쪽 이동)로 이동하거나 행렬[1][0](아래로 이동)으로 이동하고 값을 추가하여 sum=score에 도달하는 것만 이동할 수 있습니다.
예를 들어 이해합시다.
예를 들어
입력 - 행렬[행][열] ={ {1, 1}, { 1, 1} } 점수=3
출력 - 매트릭스에서 주어진 점수에 도달하는 방법의 수는 다음과 같습니다. 2
설명 - 다음과 같은 방법으로 점수에 도달할 수 있습니다.
방법 1:인덱스 (0,0) + (0,1) + (1,1) =1+1+1 =3에 요소 추가
방법 2:인덱스 (0,0) + (1,0) + (1,1) =1+1+1 =3에 요소 추가
입력 - 행렬[행][col] ={ {1,1,2},{ 2,1,1}, {1,2,2} } 점수=7
출력 - 매트릭스에서 주어진 점수에 도달하는 방법의 수는 다음과 같습니다. 2
설명 - 다음과 같은 방법으로 점수에 도달할 수 있습니다.
방법 1:인덱스 (0,0) + (0,1) + (1,1) + (1,2) + (2,2) =1+1+1+2+2 =7
방법 2:인덱스 (0,0) + (0,1) + (1,1) + (2,1) + (2,2) =1+1+1+2+2 =7
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
이 접근 방식에서는 동적 프로그래밍을 사용하여 문제를 해결합니다. 우리는 두 개의 배열을 사용할 것입니다. 배열 arr[][][]는 행렬[0][0]에서 특정 셀에 도달하는 방법의 수를 저장하는 데 사용됩니다. 재귀적으로 방법을 계산합니다.
- 숫자를 저장하기 위해 2D 배열 행렬을 사용합니다.
- 변수 점수를 입력으로 사용합니다.
- 두 개의 배열을 int arr[row][col][size] 및 bool check[row][col][size]로 가져옵니다.
- 함수 matrix_score(int matrix[row][col], int rows, int cols, int sc)는 행렬에서 주어진 점수에 도달하는 방법의 수를 반환하는 데 사용됩니다.
- 스코어 sc가 0보다 작으면 0을 반환합니다. (재귀를 종료하거나 잘못된 입력의 경우)
- 행이나 열의 수가 0보다 작으면 0을 반환합니다. (재귀를 종료하려면)
- 첫 번째 셀이 sc(입력 점수)와 같으면 유일한 방법으로 1을 반환합니다. 그렇지 않은 경우 0을 반환합니다.
- 현재 셀이 이미 방문한 경우 이 셀의 경로 수를 arr[row][cols][sc]로 반환합니다.
- 위의 모든 조건이 충족되지 않으면 현재 셀을 방문한 것으로 표시합니다. check[rows][cols][sc] =true 사용
- temp_1 계산 =matrix_score(matrix, rows-1, cols, sc-matrix[rows][cols])
- temp_2 계산 =matrix_score(matrix, rows, cols-1, sc-matrix[rows][cols])
- 방법의 수를 arr[rows][cols][sc] =temp_1 + temp_2로 설정합니다.
- 끝에 arr[rows][cols][sc]를 반환합니다.
예시
#include <iostream>
using namespace std;
#define row 2
#define col 2
#define size 30
int arr[row][col][size];
bool check[row][col][size];
int matrix_score(int matrix[row][col], int rows, int cols, int ways) {
if (ways < 0) {
return 0;
}
if (rows < 0 || cols < 0) {
return 0;
}
if (rows == 0) {
if (cols == 0) {
if (ways == matrix[0][0]) {
return 1;
} else {
return 0;
}
}
}
if (check[rows][cols][ways]) {
return arr[rows][cols][ways];
}
check[rows][cols][ways] = true;
int temp_1 = matrix_score(matrix, rows - 1, cols, ways - matrix[rows][cols]);
int temp_2 = matrix_score(matrix, rows, cols - 1, ways - matrix[rows][cols]);
arr[rows][cols][ways] = temp_1 + temp_2;
return arr[rows][cols][ways];
}
int main() {
int matrix[row][col] = {
{
1,
1
},
{
1,
1
}
};
int ways = 3;
cout << "Count of number of ways to reach a given score in a Matrix are: " << matrix_score(matrix, row - 1, col - 1, ways);
return 0;
} 위의 코드를 실행하면 다음 출력이 생성됩니다 -
출력
Count of number of ways to reach a given score in a Matrix are: 2