爆弾を \((A, B)\) に設置すると、\(A\) 行目のマスまたは \(B\) 列目のマス全てに存在する爆破対象が破壊することが出来ます。 つまり、\(A\) 行目にある爆弾の個数を\(R_A\), \(B\) 列目にある爆弾の個数を \(C_B\) とすると、およそ \(R_A + C_B\) で、爆発する爆弾の個数を求めることが出来ます。

\(A\) は\(R_A\) にしか影響を与えず、\(B\) は \(C_B\) にしか影響を与えないため、\(A, B\) それぞれを求めれば良いように思えますが、実は、爆発する個数がちょうど \(R_A + C_B\) とは限らない事が問題です。

座標 \((A,B)\) に爆発対象が存在した場合、\(R_A\) にも \(C_B\) にも値が \(1\) 足されていますが、実際の爆発対象は \(1\) つしかないため、実際に爆発する爆発対象の個数は \(R_A + C_B - 1\) となってしまいます。そこで、\(A, B\) について独立に最大値を求めた後、\(R_A\) が最大かつ \(C_B\) が最大で、\((A,B)\) に爆発対象が存在しない\((A, B)\) の組み合わせが存在するかどうかを調べる必要があります。 条件を満たす \((A, B)\)は非常に多くなりえますが、爆発対象が存在するマスは高々 \(M\) 個しか存在しないため、調べる回数は \(M\) 回以下に抑えることができ、全探索することが可能です。

これが存在するのであれば、答えは \(\max(R) + \max(C)\)、存在しないのであれば \(\max(R) + \max(C) - 1\) です。

回答例(C++, kort0n氏より引用)

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
 
int H, W, M;
set<i_i> st;
 
void input() {
    cin >> H >> W >> M;
    for(int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        st.insert({a, b});
    }
}
 
void solve() {
    map<int, int> mph, mpw;
    int hmaxval = 0;
    int wmaxval = 0;
    vector<int> hmax, wmax;
    for(auto tmp : st) {
        chmax(hmaxval, ++mph[tmp.first]);
        chmax(wmaxval, ++mpw[tmp.second]);
    }
    for(auto tmp : mph) {
        if(hmaxval == tmp.second) hmax.push_back(tmp.first);
    }
    for(auto tmp : mpw) {
        if(wmaxval == tmp.second) wmax.push_back(tmp.first);
    }
    int ANS = hmaxval + wmaxval - 1;
    for(auto h : hmax) {
        for(auto w : wmax) {
            if(st.find({h, w}) == st.end()) {
                ANS++;
                cout << ANS << endl;
                return;
            }
        }
    }
    cout << ANS << endl;
}
 
int main() {
    input();
    solve();
    return 0;
}