Chương trình C ++ để tìm ra số lượng ô tối đa mà rô bốt làm sạch có thể làm sạch trong lưới

Giả sử, chúng ta đang chế tạo một robot dọn dẹp hoạt động trên lưới điện. Lưới có kích thước h x w. Có m ô bẩn cần được làm sạch được cho trong một mảng các cặp số nguyên 'chất bẩn'. Robot làm sạch, nếu được đặt trong một ô cụ thể; có thể làm sạch mọi ô trong hàng và cột cụ thể đó. Vì vậy, nhiệm vụ của chúng ta là làm sạch số lượng ô bẩn tối đa. Chúng tôi phải tìm ra số lượng và hiển thị nó dưới dạng đầu ra.

Vì vậy, nếu đầu vào là h =3, w =3, m =3, dirty ={{0, 0}, {1, 1}, {2, 1}}, thì đầu ra sẽ là 3. Nếu chúng ta đặt rô bốt làm sạch tại ô {1, 0} thì rô bốt sẽ có thể làm sạch tất cả các ô bẩn trong lưới.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Define one map
Define two arrays hcount and wcount of size: 100 and initialize with
0
maxh = 0, maxw = 0, res = 0
Define two arrays p, q
for initialize i := 0, when i < m, update (increase i by 1), do:
   a := first value of dirt[i]
   b := second value of dirt[i]
   pairMap[pair (a, b)] := 1
   (increase hcount[a] by 1)
   (increase wcount[b] by 1)
for initialize i := 0, when i < h, update (increase i by 1), do:
   maxh := maximum of maxh and hcount[i]
for initialize i := 0, when i < w, update (increase i by 1), do:
   maxw := maximum of maxw and wcount[i]
for initialize i := 0, when i < h, update (increase i by 1), do:
   if hcount[i] is same as maxh, then:
    insert i at the end of p
for initialize i := 0, when i < w, update (increase i by 1), do:
   if wcount[i] is same as maxw, then:
   insert i at the end of q
for each element i in p, do:
   for each element j in q, do:
   if pairMap[pair (i, j)] is non-zero, then:
   res := maxh + maxw - 1
   Otherwise,
   res := maxh + maxw
   return res
return res

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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] = {0}, wcount[100] = {0}, maxh = 0, maxw = 0, res = 0;
   vector<int>p, q;
   for (int i = 0; i < m; i++) {
      int a = dirt[i].first;
      int b = dirt[i].second;
      pairMap[make_pair(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 (auto i : p) {
      for (auto j : q) {
         if (pairMap[make_pair(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

3, 3, 3, {{0, 0}, {1, 1}, {2, 1}}

Đầu ra

3