题意分析

蠕虫可以水平或垂直放置，长度至少为 2。 蠕虫不能覆盖任何石头或超出田地边界。 需要计算所有可能的水平或垂直的连续空方格序列的长度 ≥ 2 的数量。 对于每个空方格（即没有石头的方格），我们需要确定它可以作为多少个水平或垂直连续空方格序列的一部分。

对于每个空方格 (i, j)： 水平方向：向左和向右延伸，直到遇到石头或边界。计算可以形成的连续空方格序列的长度 ≥ 2 的数量。 垂直方向：向上和向下延伸，直到遇到石头或边界。计算可以形成的连续空方格序列的长度 ≥ 2 的数量。

解题思路

使用了一个二维数组la 来标记石头的位置，初始时所有位置为 false（无石头），遇到石头时标记为 true。 边界也被标记为 true（即 la[i][0]、la[i][n+1]、la[0][i]、la[m+1][i]），表示超出田地的边界。 水平方向： 对于每一行，从左到右扫描，找到连续的空方格序列。 对于每个连续的空方格序列，如果长度 ≥ 2，则计数加 1。 垂直方向： 对于每一列，从上到下扫描，找到连续的空方格序列。 对于每个连续的空方格序列，如果长度 ≥ 2，则计数加 1。 最终输出水平和垂直方向的总计数。

代码实现

#include<cstdio>
#include<cstdlib>
struct Lattice{
	int x, y;
}la[200000];
int cmpx(const void* c, const void* d){
	Lattice* a = (Lattice*)c;
	Lattice* b = (Lattice*)d;
	if (a->x == b->x) return a->y - b->y;
	else return a->x - b->x;
}
int cmpy(const void* c, const void* d){
	Lattice* a = (Lattice*)c;
	Lattice* b = (Lattice*)d;
	if (a->y == b->y) return a->x - b->x;
	else return a->y - b->y;
}
int main(){
	int T;
	scanf("%d", &T);
	while(T--){
		int m, n , k;
		scanf("%d%d%d", &m, &n, &k);
		for (int i = 0; i < k; ++i)
			scanf("%d%d", &la[i].x, &la[i].y);
		int po = 0;
		if (k == 0) po = m + n;
		else{
			qsort(la, k, sizeof(Lattice), cmpx);
			po += la[0].x - 1;
			if (la[0].y > 2) ++po;
			for (int i = 0; i < k - 1; ++i)
				if (la[i].x == la[i+1].x){
					if (la[i].y + 2 < la[i+1].y) ++po;
				}else{
					po += la[i+1].x - la[i].x - 1;
					if (la[i].y + 1 < n) ++po;
					if (la[i+1].y > 2) ++po;
				}
			if (la[k-1].y + 1 < n) ++po;
			po += m - la[k-1].x;
			qsort(la, k, sizeof(Lattice), cmpy);
			po += la[0].y - 1;
			if (la[0].x > 2) ++po;
			for (int i = 0; i < k - 1; ++i)
				if (la[i].y == la[i+1].y ){
					if (la[i].x + 2 < la[i+1].x) ++po;
				}else{
					po += la[i+1].y - la[i].y - 1;
					if (la[i].x + 1 < m) ++po;
					if (la[i+1].x > 2) ++po;
				}
			if (la[k-1].x + 1 < m) ++po;
			po += n - la[k-1].y;
		}
		printf("%d\n", po);
	}
	return 0;
}