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

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

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

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

กำหนดแมปหนึ่ง
กำหนดอาร์เรย์ hcount และ wcount ขนาด: 100 และเริ่มต้นด้วย 0
maxh = 0, maxw = 0, res = 0
กำหนดอาร์เรย์ p, q
สำหรับ i := 0, เมื่อ i < m, เพิ่ม i ขึ้นทีละ 1, ทำ:
  a := ค่าแรกของ dirt[i]
  b := ค่าที่สองของ dirt[i]
  pairMap[คู่ (a, b)] := 1
  (เพิ่ม hcount[a] ขึ้น 1)
  (เพิ่ม wcount[b] ขึ้น 1)
สำหรับ i := 0, เมื่อ i < h, เพิ่ม i ขึ้นทีละ 1, ทำ:
  maxh := สูงสุดของ maxh และ hcount[i]
สำหรับ i := 0, เมื่อ i < w, เพิ่ม i ขึ้นทีละ 1, ทำ:
  maxw := สูงสุดของ maxw และ wcount[i]
สำหรับ i := 0, เมื่อ i < h, เพิ่ม i ขึ้นทีละ 1, ทำ:
  ถ้า hcount[i] เท่ากับ maxh, แล้ว:
    ใส่ i ที่ท้ายของ p
สำหรับ i := 0, เมื่อ i < w, เพิ่ม i ขึ้นทีละ 1, ทำ:
  ถ้า wcount[i] เท่ากับ maxw, แล้ว:
    ใส่ i ที่ท้ายของ q
สำหรับแต่ละองค์ประกอบ i ใน p, ทำ:
  สำหรับแต่ละองค์ประกอบ j ใน q, ทำ:
    ถ้า pairMap[คู่ (i, j)] ไม่เป็นศูนย์, แล้ว:
      res := maxh + maxw - 1
    มิฉะนั้น
      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