第十二届北航程序设计竞赛决赛网络同步赛 J题 两点之间

题目链接  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
", 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
", max(lk + 1, spj));
			}
		}
	}

	return 0;
}