Chương trình C++ tìm số phép toán tối thiểu để tô đen hàng r cột c

Cho lưới n x m, ô đen ('B') hoặc trắng ('W'). Một phép toán: chọn ô đen, tô đen toàn bộ hàng HOẶC toàn bộ cột của nó. Tìm số phép tối thiểu để ô hàng r cột c đen. Không thể thì -1.

Ví dụ

Lưới 3x5, r=0, c=3. Đầu ra 1. Chọn ô (1,1) tô đen hàng 0.

Giải thuật

Duyệt mọi ô đen (i,j). Số phép cần = (i!=r) + (j!=c) (0, 1, hoặc 2). Lấy min. Nếu min > 2 trả về -1.

Mã 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;
}

Đầu vào / Đầu ra

Input: matrix, 0, 3
Output: 1