Cho ma trận vuông [] [] chứa các số không âm làm phần tử của nó. Cũng cho một số điểm thay đổi. Mục đích là đếm các cách để đạt được số điểm đã cho bằng cách thêm các phần tử từ ma trận [] [] sao cho chỉ các bước di chuyển được phép là di chuyển phải và di chuyển xuống.
Bắt đầu từ ma trận [0] [0] chỉ có thể di chuyển, di chuyển đến ma trận [0] [1] (di chuyển sang phải) hoặc di chuyển đến ma trận [1] [0] (di chuyển xuống) và thêm giá trị để đạt được tổng =điểm.
Hãy cho chúng tôi hiểu với các ví dụ.
Ví dụ
Đầu vào - ma trận [row] [col] ={{1, 1}, {1, 1}} điểm =3
Đầu ra - Đếm số cách đạt được điểm đã cho trong Ma trận là:2
Giải thích - Điểm số có thể đạt được bằng những cách sau:
Cách 1:thêm phần tử tại chỉ mục (0,0) + (0,1) + (1,1) =1 + 1 + 1 =3
Cách 2:thêm phần tử tại chỉ mục (0,0) + (1,0) + (1,1) =1 + 1 + 1 =3
Đầu vào - ma trận [row] [col] ={{1,1,2}, {2,1,1}, {1,2,2}} điểm =7
Đầu ra - Đếm số cách đạt được điểm đã cho trong Ma trận là:2
Giải thích - Điểm số có thể đạt được bằng những cách sau:
Cách 1:thêm phần tử tại chỉ mục (0,0) + (0,1) + (1,1) + (1,2) + (2,2) =1 + 1 + 1 + 2 + 2 =7
Cách 2:thêm phần tử tại chỉ mục (0,0) + (0,1) + (1,1) + (2,1) + (2,2) =1 + 1 + 1 + 2 + 2 =7
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 lập trình động để giải quyết vấn đề. Chúng ta sẽ sử dụng hai mảng arr [row] [col] [size] và check [row] [col] [size]. Kiểm tra mảng sẽ đánh dấu các ô của ma trận [] [] nếu chúng được truy cập là đúng. Mảng arr [] [] [] được sử dụng để lưu trữ số cách đi tới một ô cụ thể từ ma trận [0] [0]. Một cách đệ quy, chúng tôi sẽ tính toán các cách.
- Sử dụng ma trận mảng 2D để lưu trữ các số.
- Lấy điểm số thay đổi làm đầu vào.
- Lấy hai mảng int arr [row] [col] [size] và bool check [row] [col] [size].
- Điểm ma trận của hàm (int matrix [row] [col], int rows, int cols, int sc) được sử dụng để trả về số cách đạt được một điểm nhất định trong Ma trận.
- Nếu điểm sc nhỏ hơn 0 thì trả về 0. (Để kết thúc đệ quy hoặc trong trường hợp nhập sai)
- Nếu số hàng hoặc cột nhỏ hơn 0 thì trả về 0. (để kết thúc đệ quy).
- Nếu ô đầu tiên bằng sc (điểm đầu vào) thì trả về 1 là cách duy nhất. Nếu không thì trả về 0.
- Nếu ô hiện tại đã được truy cập, thì trả về số cách tại ô này dưới dạng arr [row] [cols] [sc].
- Nếu tất cả các điều kiện trên không được giữ, hãy đánh dấu ô hiện tại là đã thăm. Sử dụng dấu kiểm [row] [cols] [sc] =true.
- Tính temp_1 =matrix_score (ma trận, hàng-1, cột, ma trận sc [hàng] [cột])
- Tính temp_2 =matrix_score (ma trận, hàng, cột-1, ma trận sc [hàng] [cột])
- Đặt số cách làm arr [row] [cols] [sc] =temp_1 + temp_2.
- Cuối cùng, trả về arr [row] [cols] [sc].
Ví dụ
#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;
} Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -
Đầu ra
Count of number of ways to reach a given score in a Matrix are: 2