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

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

ดังนั้น หากอินพุตเป็น h =3, w =3, m =3, dirt ={{0, 0}, {1, 1}, {2, 1}} ผลลัพธ์จะเป็น 3 หากเรา วางหุ่นยนต์ทำความสะอาดที่เซลล์ {1, 0} จากนั้นจะสามารถทำความสะอาดเซลล์สกปรกทั้งหมดในกริดได้

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

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

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#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;
}

อินพุต

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

ผลลัพธ์

3