掃除ロボットがグリッド内で掃除できるセルの最大数を見つけるためのC++プログラム

グリッド上で動作する掃除ロボットを作っているとしましょう。グリッドの寸法はhxwです。整数ペア「dirt」の配列で指定された、クリーニングが必要なダーティセルが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