โปรแกรม C++ หาจำนวนการดำเนินการเพื่อเพิ่มจำนวนเซลล์เลขคู่ในกริดให้สูงสุด

สมมติว่าเราได้รับกริดขนาด h × w ซึ่งทุกเซลล์ในกริดมีค่าเฉพาะตัวที่กำหนดไว้ เราต้องการเพิ่มจำนวนเซลล์ที่มีค่าเป็นเลขคู่ให้มากที่สุด โดยสามารถทำได้โดยการเลือกเซลล์ที่ยังไม่เคยเลือก แล้วลดค่าของเซลล์นั้นลง 1 และเพิ่มค่าของเซลล์ที่อยู่ติดกันในแนวตั้งหรือแนวนอนขึ้น 1 โปรแกรมจะแสดงผลลัพธ์เป็นจำนวนการดำเนินการ และตำแหน่งของเซลล์ที่ลดและเพิ่มค่า ในรูปแบบดังนี้:

• จำนวนการดำเนินการ
• ตำแหน่งเซลล์ที่ลด - ตำแหน่งเซลล์ที่เพิ่ม (สำหรับแต่ละขั้นตอน)

ตัวอย่างเช่น หากอินพุตคือ h = 3, w = 3, grid = {{2, 3, 4}, {2, 0, 1}, {1, 2, 3}} ผลลัพธ์จะเป็น:

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

ขั้นตอนการแก้ปัญหา

1. สร้างอาร์เรย์ result เพื่อเก็บลำดับการดำเนินการ (tuple 4 ค่า)
2. วนลูปแถว (i = 0 ถึง h-1):
   • กำหนดตัวแปร tp = 0
   • วนลูปคอลัมน์ (j = 0 ถึง w-1):
     • ถ้า tp > 0 ให้เพิ่ม tuple (i, j-1, i, j) เข้า result และเพิ่ม grid[i][j] += tp
     • ถ้า grid[i][j] % 2 == 1 และ j < w-1 ให้ลด grid[i][j]-- และตั้ง tp = 1
     • มิฉะนั้นตั้ง tp = 0
3. รีเซ็ต tp = 0 แล้ววนลูปแถวอีกครั้งเพื่อจัดการคอลัมน์สุดท้าย (w-1):
   • ถ้า tp > 0 เพิ่ม tuple (i-1, w-1, i, w-1) และ grid[i][w-1] += tp
   • ถ้า grid[i][w-1] % 2 == 1 ให้ลดค่าลง 1 และตั้ง tp = 1 มิฉะนั้น tp = 0
4. พิมพ์ขนาดของ result และรายการ tuple ทั้งหมด

ตัวอย่างโค้ด 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;
            }
        }
    }
    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]) << ")";
        cout << '\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;
}

อินพุต / เอาต์พุต

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)