题目描述
有一只快乐的蠕虫居住在一个m×n大小的网格中。在网格的某些位置放置了k块石头。网格中的每个位置要么是空的，要么放置了一块石头。当蠕虫睡觉时，它在水平方向或垂直方向上躺着，把身体尽可能伸展开来。蠕虫的身躯既不能进入到放有石块的方格中，也不能伸出网格外。而且蠕虫的长度不会短于2个方格的大小。
本题的任务是给定网格，要计算蠕虫可以在多少个不同的位置躺下睡觉。
输入
输入文件的第1行是一个整数t，1<=t<=11,表示测试数据的个数。每个测试数据的第1行为3个整数：m,n和k(0<=m,n,k<=200000),接下来有k行，每行为2个整数，描述了一块石头的位置（行和列，最左上角位置为（1,1））。
输出
对每个测试数据，输出占一行，为一个整数，表示蠕虫可以躺着睡觉的不同位置的数目。
样例输入 复制
1
5 5 6
1 5
2 3
2 4
4 2
4 3
5 1样例输出 复制
9问题分析：
首先要理解题目的意思。题目中有两句话很关键：“当蠕虫睡觉时，它在水平方向或垂直方向上躺着，把身体尽可能伸展开来”，“而且蠕虫的长度不会短于2个方格的大小”。这两句话要结合起来理解。样例输入中的第1个测试数据的网格如图9-1（a）所示，“□”表示空的方格，“■”表示石头。如果只凭第2句话，则仅在第1列，蠕虫就可以在3个位置上躺着，分别是头在（1,1）、（2,1）、（3,1）这3个位置，身躯在垂直方向向上向下伸展开来；但加上第1句话，则这3个位置都是一样的，因为蠕虫在第1列上躺着，它的身躯会尽可能伸展开来，占满第1列所有4个空格。
对图（a）所示的网格，蠕虫可以在9个位置上躺着，这9个位置分别是：第1列、第2列、第4列、第5列、第1行、第2行、第3行、第4行和第5行。如果把（4,2）这个位置上的石头去掉，则统计出的位置数是10个。因为在第4行（4,3）位置上石头的左边和右边都满足题目的要求。
本题测试数据中的3个值取值都很大（0<=m,n,k<=200000）,如果要把整个网格用二维数组保存起来，内存使用量会超出题目的要求。即使能把整个网格保存起来，扫描这个网格需要用二重循环，时间也会超时。
本题的处理方法是，在网格的边界处“添加”一些石头，如图9-1（b）所示，“●”表示添加的石头，只需要存储输入的石头位置及添加的石头位置，然后对这些石头的位置进行如下的两种二级排序：
例如，网格中原有的石头，再加上“添加”的石头，一共26个。按第一种方式排序后为：（0,1）、（0,2）、（0,3）、（0,4）、（0,5）、（1,0）、（1,5）、（1,6）、（2,0）、（2,3）、（2,4）、（2,6）、（3,0）、（3,6）、（4,0）、（4,2）、（4,3）、（4,6）、（5,0）、（5,1）、（5,6）、（6,1）、（6,2）、（6,3）、（6,4）、（6,5）。扫描这26个位置，如果前后两个位置x坐标相同，且y坐标相差大于2，则表示其为蠕虫能躺着睡觉的位置。例如（1,0）和（1,5）满足要求，对应到网格中第1行。
AC代码：
#include<stdio.h>
#include<stdlib.h>
struct In
{
int x;
int y;
}s[10000000];
int cmpx(const void *a,const void *b)//先比较x再比较y
{
struct In *c=(struct In *)a;
struct In *d=(struct In *)b;
if(c->x!=d->x)
{
return c->x-d->x;
}
return c->y-d->y;
}
int cmpy(const void*a,const void*b)
{
struct In*c=(struct In*)a;
struct In*d=(struct In*)b;
if(c->y!=d->y)
{
return c->y-d->y;
}
return c->x-d->x;
}
int main()
{
int kase,i,m,n,k,j;
scanf("%d",&kase);
while(kase--)
{
scanf("%d %d %d",&m,&n,&k);
for(i=0;i<k;i++)
{
scanf("%d %d",&s[i].x,&s[i].y);
}
for(j=1;j<=n;j++)//左右
{
s[i].x=0;
s[i].y=j;
i++;
s[i].x=m+1;
s[i].y=j;
i++;
}
for(j=1;j<=m;j++)
{
s[i].x=j;
s[i].y=0;
i++;
s[i].y=n+1;
s[i].x=j;
i++;
}
int t=0;
qsort(s,i,sizeof(s[0]),cmpx);//横躺着的情况
for(j=0;j<i-1;j++)
{
if(s[j].x==s[j+1].x&&s[j+1].y-s[j].y>2)
{
t++;
}
}
qsort(s,i,sizeof(s[0]),cmpy);//竖着躺的情况
for(j=0;j<i-1;j++)
{
if(s[j].y==s[j+1].y&&s[j+1].x-s[j].x>2)
{
t++;
}
}
printf("%d\n",t);
}
return 0;
}