백준 10045 - JOI Emblem

문제 링크 : https://www.acmicpc.net/problem/10045

크롬의 한국어 번역기를 통해 문제를 읽어보자!

NxM 격자에서 한지점을 J,O,I중 하나로 바꿔서
JOI 의 플래그의 등장횟수의 최댓값을 찾는 문제이다

브루투포스 태그가 달리긴 했지만 그냥 생으로 완전탐색하면
(N*M 지점중 하나를 바꾼 후 N*M에서 탐색진행)
O(N^2 * M^2) 라서 1초를 넘기게 된다.

그래서 먼저

바꾸지 않은 상태의 격자판에서 JOI플래그가 등장하는 횟수(ans)를 구한 후

N*M 를 살펴보면서 J,O,I 중 하나로 바꿔주는데

이때 바꾼 지점의 근처만 보게 되면 연산 횟수를 기존의 N*M에서
4회로 줄일 수 있게된다.

바꾼 지점을 x,y 라 하면
x-1 ~ x+1 , y-1 ~ y+1 의 3x3 의 정사각형에서만
바꾸기 전의 JOI플래그 개수(bef)
바꾼 후 JOI플래그 개수(aft) 의 차이를 구한 후 diff 에 저장한다

N*M의 탐색을 끝낸 후 ans에다가 diff를 더해주면 된다.

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
int M,N;
vector<char> v[1001];
char arr[2][2];
char JOI[3] = {'J','O','I'};
int all(){
    int ret = 0;
    for(int i=0;i<M-1;i++){
        for(int t=0;t<N-1;t++){
            char a = v[i][t];
            char b = v[i][t+1];
            char c = v[i+1][t];
            char d = v[i+1][t+1];
            if(a==arr[0][0]&&b==arr[0][1]&&c==arr[1][0]&&d==arr[1][1]){
                ret++;
            }
        }
    }
    return ret;
}
int dx[4]={-1,0,-1,0};
int dy[4]={-1,-1,0,0};
int find(int x,int y){
    int ret = 0;
    for(int i=0;i<4;i++){
        int nx = x+dx[i];int ny = y+dy[i];
        if(nx<0||nx+1>=N||ny<0||ny+1>=M) continue;
        char a = v[ny][nx];
        char b = v[ny][nx+1];
        char c = v[ny+1][nx];
        char d = v[ny+1][nx+1];
        if(a==arr[0][0]&&b==arr[0][1]&&c==arr[1][0]&&d==arr[1][1]) ret++;
    }
    return ret;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>M>>N;
    for(int i=0;i<M;i++){
        string a;cin>>a;
        for(int t=0;t<a.length();t++){
            v[i].push_back(a[t]);
        }
    }
    for(int i=0;i<2;i++){
        for(int t=0;t<2;t++){
            cin>>arr[i][t];
        }
    }
    int ans = 0;int diff = 0;
    ans = max(ans,all());
    for(int i=0;i<M;i++){
        for(int t=0;t<N;t++){
            char a = v[i][t];int bef,aft=0;
            bef = find(t,i);
            for(int j=0;j<3;j++){
                if(JOI[j]==a) continue;
                v[i][t]=JOI[j];
                aft = max(aft,find(t,i));
            }
            diff = max(diff,aft-bef);
            v[i][t]=a;
        }
    }
    cout<<ans+diff<<"\n";
}