题解：P15811 [JOI 2014 Final] JOI 徽章 / JOI Emblem

  1  2  3
1 ·  ·  ·
2 ·  X  ·
3 ·  ·  ·

考虑到修改一点的字符只会影响周围的包含该字符的 4 个徽章（$2 \times 2$ 的格子）是否合法（如上图，更改 $(2, 2)$ 的符号，只影响左上角为 $(1, 1)$，$(1, 2)$，$(2, 1)$，$(2, 2)$ 这四个徽章），且 $n,m \le 1000$，于是决定使用枚举的方法。

首先统计不修改的情况下能形成多少个合法徽章，直接遍历一遍所有的徽章是否合法即可。

然后枚举所有可修改的点，对于每一个点的每一种修改情况，判断其周围 4 个徽章原先是否合法，修改后是否合法，然后更新答案就好了。

时间复杂度 $\mathcal{O}(nm)$。

代码

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

const int N = 1e3 + 10;
const int pos[4][2] = {0, 0, 0, 1, 1, 0, 1, 1};

const char mark[3] = {'J', 'O', 'I'};

int n, m;
char flag[N][N];
char emb[2][2];

bool com[N][N];
int ans = 0;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n >> m;
	
	for (int i = 1; i <= n; ++i)
		for (int j = 1; j <= m; ++j)
			cin >> flag[i][j];
			
	for (int i = 0; i < 2; ++i)
		for (int j = 0; j < 2; ++j)
			cin >> emb[i][j];
	
	for (int x = 1; x <= n - 1; ++x) {
		for (int y = 1; y <= m - 1; ++y) {
			com[x][y] = 1;
			
			for (int k = 0; k < 4; ++k) {
				int xi = x + pos[k][0];
				int yi = y + pos[k][1];
				
				if (flag[xi][yi] != emb[pos[k][0]][pos[k][1]]) {
					com[x][y] = 0;
					break;
				}
			}
			
			ans += com[x][y] ? 1 : 0;
		}
	}
	
	int base = ans;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			int del = 0;
			
			for (int dx = -1; dx <= 0; dx++) {
				for (int dy = -1; dy <= 0; dy++) {
					int x = i + dx;
					int y = j + dy;
					
					if (x >= 1 && x <= n - 1 && y >= 1 && y <= m - 1)
						del += com[x][y];
				}
			}

			char ori = flag[i][j];
			
			for (int c = 0; c < 3; ++c) {
				int cur = base - del;
				flag[i][j] = mark[c];
				
				for (int dx = -1; dx <= 0; dx++) {
					for (int dy = -1; dy <= 0; dy++) {
						int x = i + dx;
						int y = j + dy;
						
						if (x < 1 || x > n - 1 || y < 1 || y > m - 1) continue;
						bool ok = 1;
						
						for (int h = 0; h < 4; ++h) {
							int xx = x + pos[h][0];
							int yy = y + pos[h][1];
							
							if (flag[xx][yy] != emb[pos[h][0]][pos[h][1]]) {
								ok = 0;
								break;
							}
						}
						
						cur += ok;
					}
				}
				
				ans = max(ans, cur);
			}
			
			flag[i][j] = ori;
		}
	}
	
	cout << ans;
	
return 0;
}