행 X 열 차원이 있는 2D 행렬이 제공됩니다. 목표는 오른쪽 및 아래쪽 이동만 사용하여 셀 0,0에서 셀 행, 열까지 행렬을 순회할 수 있는 방법의 수를 계산하는 것입니다. 즉, 첫 번째 이동은 0,0에서 0,1(아래로) 또는 1,0이 될 수 있습니다. (오른쪽) 1,1(대각선)이 아닙니다.
예를 들어
입력
col = 2; row = 4
출력
Count of number of ways to traverse a Matrix are: 4
설명
셀 0,0에서 2,4까지 도달할 수 있는 방법이 표시됩니다. -
입력
col = 4; row = 3
출력
Count of number of ways to traverse a Matrix are: 10
설명
We will reduce the problem into smaller recursions. Count ways for col=3, row=2, then for col=2, row=1 ….. For col=1 or row=1 the answer will be 1. (only right or only down move).
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
이 접근 방식에서는 재귀 방법을 사용합니다. 행 또는 열의 끝에는 1이 있습니다. 1개의 직선 오른쪽 이동 또는 1개의 직선 아래 이동인 한 가지 방법만 있습니다. 이것은 재귀의 종료 조건이 됩니다.
-
행렬의 차원에 대해 정수 행, 열을 사용합니다.
-
way_traverse_matrix(int row, int col) 함수는 차원을 취하고 행렬을 순회하는 방법의 수를 반환합니다.
-
row==1의 경우 1을 반환합니다.
-
col==1의 경우 1을 반환합니다.
-
그렇지 않으면 재귀 way_traverse_matrix(temp_1, col) +ways_traverse_matrix(row, temp_2)를 사용하여 방법을 계산합니다.
-
여기서 temp_1=이전 행 번호 및 temp_2=이전 열 번호입니다.
-
마지막에 우리는 총 방법의 개수를 얻을 것입니다.
예
#include <bits/stdc++.h>
using namespace std;
int ways_traverse_matrix(int row, int col){
if (row == 1){
return 1;
}
else if(col == 1){
return 1;
} else {
int temp_1 = row − 1;
int temp_2 = col − 1;
return ways_traverse_matrix(temp_1, col) + ways_traverse_matrix(row, temp_2);
}
}
int main(){
int col = 2;
int row = 2;
cout<<"Count the number of ways to traverse a Matrix are: "<<ways_traverse_matrix(row, col);
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 출력이 생성됩니다 -
Count the number of ways to traverse a Matrix are: 2