Đếm số cách duyệt ma trận trong C++

Cho một ma trận 2D với kích thước row x col. Mục tiêu là đếm số cách duyệt ma trận từ ô 0,0 đến ô row, col chỉ dùng di chuyển phải và xuống, tức là nước đi đầu tiên có thể là 0,0 đến 0,1 (xuống) hoặc 1,0 (phải) chứ không phải 1,1 (chéo).

Ví dụ

Đầu vào

col = 2; row = 4

Đầu ra

Số cách duyệt ma trận là: 4

Giải thích

Các cách để đến từ ô 0,0 đến 2,4 được hiển thị như sau:

Đầu vào

col = 4; row = 3

Đầu ra

Số cách duyệt ma trận là: 10

Giải thích

Chúng ta sẽ quy hoạch vấn đề thành các đệ quy nhỏ hơn. Đếm cách cho col=3, row=2, rồi col=2, row=1... Đối với col=1 hoặc row=1 đáp án sẽ là 1 (chỉ đi phải hoặc chỉ đi xuống).

Phương pháp sử dụng

Trong phương pháp này, chúng ta sẽ sử dụng phương pháp đệ quy. Ở cuối cho row hoặc col bằng 1. Chỉ có một cách là 1 nước đi thẳng phải hoặc 1 nước đi thẳng xuống. Đây sẽ là điều kiện dừng cho đệ quy.

• Nhận số nguyên row, col cho kích thước ma trận.
• Hàm ways_traverse_matrix(int row, int col) nhận kích thước và trả về số cách duyệt ma trận.
• Đối với row==1, trả về 1.
• Đối với col==1, trả về 1.
• Ngược lại tính số cách dùng đệ quy: ways_traverse_matrix(temp_1, col) + ways_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 ta sẽ nhận được tổng số cách.

Ví dụ mã

#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 << "Số cách duyệt ma trận là: " << ways_traverse_matrix(row, col);
    return 0;
}

Đầu ra

Nếu chạy mã trên, sẽ tạo ra đầu ra sau:

Số cách duyệt ma trận là: 2