Chương trình C++ tìm số ô bẩn tối đa robot hút bụi có thể dọn

Mô tả bài toán

Cho lưới h x w có m ô bẩn. Robot đặt tại một ô sẽ dọn sạch toàn bộ hàng và cột đó. Tìm vị trí đặt robot để dọn được nhiều ô bẩn nhất.

Ví dụ

h=3, w=3, m=3, dirt={{0,0},{1,1},{2,1}} → Output: 3.

Đặt robot tại (1,0) dọn được cả 3 ô bẩn.

Giải thuật

1. Đếm số ô bẩn trên mỗi hàng (hcount) và cột (wcount).
2. Tìm maxh (hàng nhiều bẩn nhất) và maxw (cột nhiều bẩn nhất).
3. Thu thập các hàng có maxh vào mảng p, cột có maxw vào q.
4. Duyệt các cặp (hàng ∈ p, cột ∈ q): nếu ô giao không có bẩn → kết quả = maxh+maxw; ngược lại = maxh+maxw-1.

Mã nguồn C++

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;

int solve(int h, int w, int m, vector<pair<int,int>> dirt) {
    map<pair<int,int>, int> pairMap;
    int hcount[100] = {}, wcount[100] = {}, maxh=0, maxw=0, res=0;
    vector<int> p, q;

    for (auto [a,b] : dirt) {
        pairMap[{a,b}] = 1;
        hcount[a]++; wcount[b]++;
    }
    for (int i=0; i<h; i++) maxh = max(maxh, hcount[i]);
    for (int i=0; i<w; i++) maxw = max(maxw, wcount[i]);
    for (int i=0; i<h; i++) if (hcount[i]==maxh) p.push_back(i);
    for (int i=0; i<w; i++) if (wcount[i]==maxw) q.push_back(i);

    for (int i : p) for (int j : q) {
        if (pairMap[{i,j}]) res = maxh + maxw - 1;
        else { res = maxh + maxw; return res; }
    }
    return res;
}

int main() {
    int h=3, w=3, m=3;
    vector<pair<int,int>> dirt = {{0,0},{1,1},{2,1}};
    cout << solve(h,w,m,dirt);
    return 0;
}

Đầu vào / Đầu ra

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