Chương trình C++ tìm số phép toán để tối đa hóa số ô chẵn trong lưới

Mô tả bài toán

Cho một lưới kích thước h × w, mỗi ô có một giá trị cụ thể. Mục tiêu là tối đa hóa số ô có giá trị chẵn. Được phép chọn một ô chưa từng chọn, giảm giá trị ô đó đi 1 và tăng giá trị 1 cho một ô liền kề theo chiều dọc hoặc ngang. Cần in ra số phép toán và các cặp vị trí (ô giảm - ô tăng).

Ví dụ

Với h = 3, w = 3, lưới = {{2, 3, 4}, {2, 0, 1}, {1, 2, 3}} thì đầu ra:

4 (0, 1) - (0, 2) (2, 0) - (2, 1) (2, 1) - (2, 2) (0, 2) - (1, 2)

Thuật toán

1. Duyệt từng hàng từ trái sang phải, giữ biến tp (0 hoặc 1) chỉ việc có "mang" dư 1 từ ô trước.
2. Nếu tp > 0, ghi nhận phép toán từ ô trước sang ô hiện tại, cộng tp vào ô hiện tại.
3. Nếu ô hiện tại lẻ (grid[i][j] % 2 == 1) và không phải cột cuối, giảm ô đó 1 và đặt tp = 1.
4. Sau khi duyệt xong các hàng, duyệt cột cuối cùng theo chiều dọc tương tự để xử lý các ô lẻ còn sót.
5. In số lượng phép toán và danh sách các cặp tọa độ.

Đoạn mã C++

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

void solve(int h, int w, vector<vector<int>> grid) {
    vector<tuple<int,int,int,int>> result;
    for(int i = 0; i < h; i++) {
        int tp = 0;
        for(int j = 0; j < w; j++) {
            if(tp > 0) {
                result.push_back(make_tuple(i, j-1, i, j));
                grid[i][j] += tp;
            }
            if(grid[i][j] % 2 == 1 && j < w-1) {
                grid[i][j] -= 1;
                tp = 1;
            } else tp = 0;
        }
    }
    int tp = 0;
    for(int i = 0; i < h; i++) {
        if(tp > 0) {
            result.push_back(make_tuple(i-1, w-1, i, w-1));
            grid[i][w-1] += tp;
        }
        if(grid[i][w-1] % 2 == 1) {
            grid[i][w-1] -= 1;
            tp = 1;
        } else tp = 0;
    }
    cout << (int)result.size() << endl;
    for(int i = 0; i < (int)result.size(); i++) {
        cout << "(" << get<0>(result[i]) << ", " << get<1>(result[i])
             << ") - (" << get<2>(result[i]) << ", " << get<3>(result[i]) << ")\n";
    }
}

int main() {
    int h = 3, w = 3;
    vector<vector<int>> grid = {{2, 3, 4}, {2, 0, 1}, {1, 2, 3}};
    solve(h, w, grid);
    return 0;
}

Đầu vào / Đầu ra

Input: 3, 3, {{2, 3, 4}, {2, 0, 1}, {1, 2, 3}}

Output: 4 (0, 1) - (0, 2) (2, 0) - (2, 1) (2, 1) - (2, 2) (0, 2) - (1, 2)