Tổng khối ma trận trong C++

Cho một ma trận m x n tên là mat và một số nguyên K, ta cần tìm ma trận answer trong đó mỗi answer[i][j] là tổng của tất cả các phần tử mat[r][c] thỏa mãn i - K <= r <= i + K, j - K <= c <= j + K, và (r, c) là vị trí hợp lệ trong ma trận.

Ví dụ với ma trận:

Với k = 1, kết quả:

Giải thuật

1. n = số hàng, m = số cột.
2. Khởi tạo ma trận ans kích thước n x m.
3. Duyệt qua mỗi ô (i, j):
4. Duyệt qua vùng [i-k, i+k] x [j-k, j+k].
5. Nếu (r, c) hợp lệ, cộng mat[r][c] vào ans[i][j].
6. Trả về ans.

Ví dụ C++

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<vector<auto> > v) {
    cout << "[";
    for(int i = 0; i < v.size(); i++) {
        cout << "[";
        for(int j = 0; j < v[i].size(); j++) cout << v[i][j] << ", ";
        cout << "],";
    }
    cout << "]" << endl;
}

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int n = mat.size();
        int m = mat[0].size();
        vector<vector<int>> ans(n, vector<int>(m));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                for(int r = i - k; r <= i + k; r++) {
                    for(int c = j - k; c <= j + k; c++) {
                        if(r >= 0 && r < n && c >= 0 && c < m) {
                            ans[i][j] += mat[r][c];
                        }
                    }
                }
            }
        }
        return ans;
    }
};

int main() {
    vector<vector<int>> v1 = {{1,2,3},{4,5,6},{7,8,9}};
    Solution ob;
    print_vector(ob.matrixBlockSum(v1, 1));
    return 0;
}

Đầu vào

[[1,2,3],[4,5,6],[7,8,9]] 1

Đầu ra

[[12, 21, 16, ],[27, 45, 33, ],[24, 39, 28, ],]