C++で解く掃除ロボット問題：グリッド上で清掃できる汚れセルの最大数を求める方法

問題概要

h × w のサイズを持つグリッド上で動作する掃除ロボットを開発することを考えてみましょう。グリッドには m 個の汚れたセルがあり、それらは整数ペアの配列 dirt として与えられます。この掃除ロボットには特別な機能があり、特定のセルに配置すると、そのセルが属する「行」と「列」のすべてのセルを一度に掃除できます。私たちのタスクは、ロボットを最適な位置に配置したときに、最大で何個の汚れたセルを掃除できるかを求め、その数を出力することです。

例えば、入力が h = 3、w = 3、m = 3、dirt = {{0, 0}, {1, 1}, {2, 1}} の場合、出力は 3 になります。これは、ロボットをセル {1, 0} に配置することで、グリッド上のすべての汚れたセルを掃除できるためです。

解法のアプローチ

この問題は、以下の手順で効率的に解くことができます。

1. 汚れたセルの座標を記録するためのマップ（pairMap）を用意します。
2. 各行に含まれる汚れセルの数を数える配列 hcount と、各列に含まれる汚れセルの数を数える配列 wcount を用意します。
3. 汚れセル数が最大となる行の値 maxh と、列の値 maxw をそれぞれ求めます。
4. maxh に一致する行インデックスを配列 p に、maxw に一致する列インデックスを配列 q に格納します。
5. p と q のすべての組み合わせについて交点となるセルを確認します。そのセルが汚れている場合は同じセルを二重にカウントしないよう maxh + maxw − 1 を、そうでない場合は maxh + maxw を答えとして返します。

このアプローチにより、全セルを総当たりするよりもはるかに効率的に答えを導き出せます。計算量は汚れセルの数 m と候補となる行・列の組み合わせに依存します。

C++実装例

それでは、実際のコード実装を見ていきましょう。

#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

まとめ

このプログラムでは、まず各行・各列の汚れセル数を集計し、最も多くの汚れを含む行と列の組み合わせを探索します。交点のセルがすでに汚れている場合のみカウントを1つ減らすことで、重複を正確に排除しています。この手法を使えば、掃除ロボットが一度の配置で清掃できる汚れセルの最大数を簡単に求めることができます。