मान लीजिए, हम एक सफाई रोबोट बना रहे हैं जो ग्रिड पर काम करता है। ग्रिड आयाम h x w का है। वहाँ m गंदी कोशिकाएँ हैं जिन्हें साफ करने की आवश्यकता है जो पूर्णांक जोड़े 'गंदगी' की एक सरणी में दी गई हैं। सफाई रोबोट, यदि किसी विशेष सेल में रखा गया हो; उस विशेष पंक्ति और स्तंभ में प्रत्येक कक्ष को साफ़ कर सकते हैं। तो हमारा काम ज्यादा से ज्यादा संख्या में गंदी कोशिकाओं को साफ करना है। हमें गिनती का पता लगाना है और इसे आउटपुट के रूप में प्रदर्शित करना है।
इसलिए, यदि इनपुट h =3, w =3, m =3, डर्ट ={{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