Đếm số cách đạt điểm cho trước trong ma trận bằng C++

Cho ma trận vuông matrix[][] chứa số không âm. Cho biến score. Mục tiêu: đếm số cách đạt được score bằng cách cộng các phần tử từ matrix[][] chỉ cho phép đi phải và xuống.

Bắt đầu từ matrix[0][0], chỉ được đi sang matrix[0][1] (phải) hoặc matrix[1][0] (xuống) và cộng giá trị để đạt tổng = score.

Hiểu qua ví dụ

Đầu vào: matrix[2][2] = {{1, 1}, {1, 1}}, score = 3

Đầu ra: Số cách đạt điểm: 2

Giải thích: Cách 1: (0,0)+(0,1)+(1,1)=3. Cách 2: (0,0)+(1,0)+(1,1)=3.

Đầu vào: matrix[3][3] = {{1,1,2},{2,1,1},{1,2,2}}, score = 7

Đầu ra: Số cách đạt điểm: 2

Giải thích: Cách 1: (0,0)+(0,1)+(1,1)+(1,2)+(2,2)=7. Cách 2: (0,0)+(0,1)+(1,1)+(2,1)+(2,2)=7.

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

Sử dụng quy hoạch động với hai mảng arr[row][col][size] và check[row][col][size]. check đánh dấu ô đã thăm. arr[][][] lưu số cách đến ô từ matrix[0][0]. Tính đệ quy.

• Nhập mảng 2D matrix và score.
• Hai mảng int arr[row][col][size], bool check[row][col][size].
• Hàm matrix_score(int matrix[row][col], int rows, int cols, int sc) trả về số cách.
• Nếu trả về 0.
• Nếu trả về 0.
• Nếu ô đầu (0,0) bằng sc trả về 1, ngược lại 0.
• Nếu ô hiện tại đã thăm trả về arr[rows][cols][sc].
• Đánh dấu đã thăm: 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.
• Trả về arr[rows][cols][sc].

Ví dụ mã nguồn

#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; 
}

Chạy mã trên cho kết quả:

Kết quả

Count of number of ways to reach a given score in a Matrix are: 2