JOI2014 本選1 解説

A - JOI 紋章 (JOI Emblem)

まず最初に、全体での答えを求めておき、次に1箇所だけ変えた時に答えがどれだけ変わるかを計算すると解けます。計算量は $O(MN)$ です。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int M, N;
    cin >> M >> N;
    vector<string> S(M);
    for (int i = 0; i < M; i++) {
        cin >> S[i];
    }
    vector<string> E(2);
    cin >> E[0] >> E[1];
    auto isok = [&](int x, int y) -> bool {
        return (S[x][y] == E[0][0] && S[x][y + 1] == E[0][1] && S[x + 1][y] == E[1][0] && S[x + 1][y + 1] == E[1][1]);
    };
    int now = 0;
    for (int i = 0; i < M - 1; i++) {
        for (int j = 0; j < N - 1; j++) {
            now += isok(i, j);
        }
    }
    int ans = now;
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            char c = S[i][j];
            int cnt = 0;
            for (int k = max(0, i - 1); k < min(M - 1, i + 1); k++) {
                for (int l = max(0, j - 1); l < min(N - 1, j + 1); l++) {
                    cnt += isok(k, l);
                }
            }
            for (char nc: "JOI") {
                S[i][j] = nc;
                int cnt2 = 0;
                for (int k = max(0, i - 1); k < min(M - 1, i + 1); k++) {
                    for (int l = max(0, j - 1); l < min(N - 1, j + 1); l++) {
                        cnt2 += isok(k, l);
                    }
                }
                ans = max(ans, now - cnt + cnt2);
            }
            S[i][j] = c;
        }
    }
    cout << ans << '\n';
}