题目链接 Problem J
这道题思路还是很直观的，但是有两个难点：
1、题目中说$1<=NM<=10^{6}$，但没具体说明$N$和$M$的值，也就是可能出现：
$N = 1, M = 1000000$ 这样的数据。
2、对每个查询的分类讨论。
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i(0); i < (n); ++i)
#define rep(i,a,b) for(int i(a); i <= (b); ++i)
#define dec(i,a,b) for(int i(a); i >= (b); --i)
#define for_edge(i,x) for(int i = H[x]; i; i = X[i]) const int N = 1000000 + 10;
const int Q = 1000 + 10; struct node{
int num, x, y, id;
} c[N], f[N]; int ret[Q], nc[Q], nd[Q], ne[Q], ccc[Q]; int ct[N];
int n, m, q;
int cnt;
char st[N];
int T;
int v[N], t[N];
int l, r;
int color;
int col[N];
int x, y; struct nnnn{
int x, y;
} nf[6]; inline bool check(int nu, int pos){
if (nu < 1 || nu > cnt) return false;
if (v[nu]) return false;
int xx1 = c[nu].x, yy1 = c[nu].y, xx2 = c[pos].x, yy2 = c[pos].y;
if (xx1 < 1 || xx1 > n || yy1 < 1 || yy1 > m) return false;
if (abs(xx1 - xx2) + abs(yy1 - yy2) != 1) return false;
if (c[nu].num != c[pos].num) return false;
return true;
} inline bool cc(int nu, int pos){
if (nu < 1 || nu > cnt) return false;
int xx1 = c[nu].x, yy1 = c[nu].y, xx2 = c[pos].x, yy2 = c[pos].y;
if (xx1 < 1 || xx1 > n || yy1 < 1 || yy1 > m) return false;
if (abs(xx1 - xx2) + abs(yy1 - yy2) != 1) return false;
return true;
} inline int pos(int x, int y){ return (x - 1) * m + y;} inline void work(int nu){
t[nu] = color;
f[++r].x = c[nu].x,
f[r].y = c[nu].y,
f[r].id = nu;
v[nu] = 1;
} int main(){ scanf("%d", &T);
while (T--){
scanf("%d%d%d", &n, &m, &q);
cnt = 0;
rep(i, 1, n){
scanf("%s", st + 1);
rep(j, 1, m) ++cnt,
c[cnt].num = (int)st[j] - 48,
c[cnt].x = i, c[cnt].y = j;
} color = 0;
rep(i, 1, cnt) v[i] = 0, t[i] = 0;
rep(i, 1, cnt) if (v[i] == 0){
++color;
t[i] = color;
ct[color] = c[i].num;
f[1].x = c[i].x,
f[1].y = c[i].y,
f[1].id = i;
for (l = r = 1; l <= r; ++l){
int now = f[l].id;
if (check(now - 1, now)) work(now - 1);
if (check(now + 1, now)) work(now + 1);
if (check(now - m, now)) work(now - m);
if (check(now + m, now)) work(now + m);
}
} int maxcol = 0;
rep(i, 1, cnt) col[i] = 0;
int ta = 0;
rep(i, 1, n){
rep(j, 1, m){
++ta;
++col[t[ta]];
maxcol = max(maxcol, t[ta]);
}
} while (q--){
scanf("%d%d", &x, &y);
int df = 0, np = pos(x, y);
if (cc(np - 1, np)) ret[++df] = np - 1;
if (cc(np + 1, np)) ret[++df] = np + 1;
if (cc(np - m, np)) ret[++df] = np - m;
if (cc(np + m, np)) ret[++df] = np + m; rep(i, 1, df) nc[i] = t[ret[i]];
sort(nc + 1, nc + df + 1);
nd[1] = nc[1];
int dx = 1;
rep(i, 2, df) if (nc[i] != nc[i - 1]) nd[++dx] = nc[i];
bool fl = false;
rep(i, 1, dx) if (nd[i] == t[np]){ fl = true; break;} if (!fl){
rep(i, 1, dx) ne[i] = ct[nd[i]];
rep(i, 0, 9) ccc[i] = 0;
rep(i, 1, dx) ccc[ne[i]] += col[nd[i]];
int lk = 0; rep(i, 0, 9) lk = max(lk, ccc[i]);
printf("%d\n", lk + 1);
} else
{
int spj = 0; rep(i, 1, dx) if (nd[i] == t[np]) spj += col[nd[i]];
int dd = 0; rep(i, 1, dx) if (nd[i] != t[np]) nf[++dd].x = ct[nd[i]], nf[dd].y = nd[i];
rep(i, 0, 9) ccc[i] = 0; rep(i, 1, dd) ccc[nf[i].x] += col[nf[i].y];
int lk = 0; rep(i, 0, 9) lk = max(lk, ccc[i]);
printf("%d\n", max(lk + 1, spj));
}
}
} return 0;
}