Cho ma trận 2D với hàng kích thước X col. Mục đích là đếm số cách người ta có thể duyệt ma trận từ ô 0,0 đến hàng ô, col chỉ sử dụng các lần di chuyển phải và xuống, tức là lần di chuyển đầu tiên có thể là 0,0 đến 0,1 (xuống dưới) hoặc 1,0 (phải) chứ không phải 1,1 (đường chéo).
Ví dụ
Đầu vào
col = 2; row = 4
Đầu ra
Count of number of ways to traverse a Matrix are: 4
Giải thích
Các cách mà chúng ta có thể tiếp cận từ ô 0,0 đến 2,4 được hiển thị -
Đầu vào
col = 4; row = 3
Đầu ra
Count of number of ways to traverse a Matrix are: 10
Giải thích
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).
Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau
Trong cách tiếp cận này, chúng tôi sẽ sử dụng một phương pháp đệ quy. Cuối cùng cho hàng hoặc cột là 1. Chỉ có một cách là 1 bước đi thẳng sang phải hoặc 1 bước đi thẳng xuống. Đây sẽ là điều kiện kết thúc cho đệ quy.
-
Lấy số nguyên hàng, col cho kích thước của ma trận.
-
Hàm styles_traverse_matrix (int row, int col) nhận các kích thước và trả về số lượng các cách để duyệt qua Ma trận.
-
Đối với hàng ==1, trả về 1.
-
Đối với col ==1, trả về 1.
-
Các cách tính toán khác bằng cách sử dụng đệ quy way_traverse_matrix (temp_1, col) + way_traverse_matrix (row, temp_2).
-
Đây temp_1 =số hàng trước đó và temp_2 =số cột trước đó.
-
Cuối cùng, chúng tôi sẽ nhận được tổng số cách.
Ví dụ
#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;
} Đầu ra
Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Count the number of ways to traverse a Matrix are: 2