ধরি, আমরা একটি ক্লিনিং রোবট তৈরি করছি যা একটি গ্রিডে কাজ করে। গ্রিডটির মাত্রা h x w। m সংখ্যক ময়লা সেল আছে যা পরিমার্জন করতে হবে, সেগুলো 'dirt' নামক একটি ইন্টিজার পেয়ারের অ্যারেতে দেওয়া আছে। ক্লিনিং রোবট যদি কোনো নির্দিষ্ট সেলে রাখা হয়, তবে সেটি সেই সারিটি এবং কলামটির সব সেল পরিমার্জন করতে পারে। তাহলে আমাদের কাজ হল সর্বোচ্চ সংখ্যক ময়লা সেল পরিমার্জন করা। সেটির গণনা করে আউটপুট হিসেবে দেখাতে হবে।
উদাহরণস্বরূপ, ইনপুট h = 3, w = 3, m = 3, dirt = {{0, 0}, {1, 1}, {2, 1}} হলে আউটপুট হবে ৩। যদি ক্লিনিং রোবটকে {1, 0} সেলে রাখা হয়, তবে সেটি গ্রিডের সব ময়লা সেল পরিমার্জন করতে পারবে।
সমাধানের পদ্ধতি
একটি map ডিফাইন করুন
১০০ আকারের দুটি অ্যারে hcount এবং wcount ডিফাইন করুন এবং ০ দিয়ে ইনিশিয়ালাইজ করুন
maxh = 0, maxw = 0, res = 0
দুটি অ্যারে p, q ডিফাইন করুন
i = 0 থেকে m-1 পর্যন্ত:
a := dirt[i]-এর প্রথম মান
b := dirt[i]-এর দ্বিতীয় মান
pairMap[pair (a, b)] := 1
(hcount[a] ১ বাড়ান)
(wcount[b] ১ বাড়ান)
i = 0 থেকে h-1 পর্যন্ত:
maxh := maxh এবং hcount[i]-এর মধ্যে সর্বোচ্চ
i = 0 থেকে w-1 পর্যন্ত:
maxw := maxw এবং wcount[i]-এর মধ্যে সর্বোচ্চ
i = 0 থেকে h-1 পর্যন্ত:
if hcount[i] == maxh, তবে:
p-তে i যোগ করুন
i = 0 থেকে w-1 পর্যন্ত:
if wcount[i] == maxw, তবে:
q-তে i যোগ করুন
p-র প্রতিটি এলিমেন্ট i-এর জন্য:
q-র প্রতিটি এলিমেন্ট j-এর জন্য:
if pairMap[pair (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
