โปรแกรม C++ หาจำนวนครั้งน้อยที่สุดทาสีแถว/คอลัมน์ให้เซลล์เป้าหมายเป็นสีดำ

คำอธิบายปัญหา

สมมติว่าเรามีตัวเลข r, c และกริดขนาด n x m บางเซลล์เป็นสีดำ ส่วนที่เหลือสีขาว ใน 1 ครั้ง สามารถเลือกเซลล์ดำบางเซลล์ และทำได้เพียงอย่างใดอย่างหนึ่ง:

• ทาสีดำทั้งแถวของเซลล์นั้น, หรือ
• ทาสีดำทั้งคอลัมน์ของเซลล์นั้น

ตัวอย่าง: กริด 3x5 ตามตาราง r=0, c=3 ผลลัพธ์คือ 1 เพราะทาแถวแรกหมดจะทำให้เซลล์ (0,3) เป็นสีดำ

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

n := จำนวนแถวของกริด
m := จำนวนคอลัมน์ของกริด
ans := infinity
สำหรับ i := 0 ถึง n-1:
    สำหรับ j := 0 ถึง m-1:
        ถ้า matrix[i,j] == 'B':
            ans := min(ans, (i != r ? 1 : 0) + (j != c ? 1 : 0))
ถ้า ans > 2: คืนค่า -1
มิฉะนั้น: คืนค่า ans

ตัวอย่างโค้ด C++

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

int solve(vector<vector<char>> matrix, int r, int c) {
    int n = matrix.size();
    int m = matrix[0].size();
    int ans = 999999;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (matrix[i][j] == 'B') {
                ans = min(ans, (i != r) + (j != c));
            }
        }
    }
    if (ans > 2) {
        return -1;
    } else {
        return ans;
    }
}

int main() {
    vector<vector<char>> matrix = { { 'W', 'B', 'W', 'W', 'W' },
                                     { 'B', 'B', 'B', 'W', 'B' },
                                     { 'W', 'W', 'B', 'B', 'B' } };
    int r = 0, c = 3;
    cout << solve(matrix, r, c) << endl;
}

อินพุต

{ { 'W', 'B', 'W', 'W', 'W' }, { 'B', 'B', 'B', 'W', 'B' }, { 'W', 'W', 'B', 'B', 'B' } }, 0, 3

เอาต์พุต

1