1974.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include<stdio.h>
#include<stdlib.h>

#define debug 0


#define NMAX 1000003

    
struct data
{
   long x,y;
}v[NMAX];

long t,m,n,k;
long count;

int cmp1(void const *a,void const *b)
{
    if((*(struct data*)a).y==(*(struct data*)b).y)
        return (*(struct data*)a).x-(*(struct data*)b).x;
    else
        return (*(struct data*)a).y-(*(struct data*)b).y;
}

int cmp2(void const *a,void const *b)
{
    if((*(struct data*)a).x==(*(struct data*)b).x)
        return (*(struct data*)a).y-(*(struct data*)b).y;
    else
        return (*(struct data*)a).x-(*(struct data*)b).x;
}
void solve()
{

    int i;
    qsort(v,k,sizeof(struct data),cmp1);

	int sum=0;
//	cy=v[0].y;
	if(v[0].x>2)
		sum++;
	sum+=v[0].y-1;
	for(i=1;i<k;i++)
	{
		if(v[i].y==v[i-1].y)
		{
			if(v[i].x-v[i-1].x>2)
				sum++;
		}
		else
		{
			sum+=v[i].y-v[i-1].y-1;
			if(n+1-v[i-1].x>2)
				sum++;
			if(v[i].x>2)
				sum++;
		}
	}
	if(n+1-v[i-1].x>2)
		sum++;
	sum+=m-v[i-1].y;
	qsort(v,k,sizeof(struct data),cmp2);

	if(v[0].y>2)
		sum++;
	sum+=v[0].x-1;
	for(i=1;i<k;i++)
	{
		if(v[i].x==v[i-1].x)
		{
			if(v[i].y-v[i-1].y>2)
				sum++;
		}
		else
		{
			sum+=v[i].x-v[i-1].x-1;
			if(m+1-v[i-1].y>2)
				sum++;
			if(v[i].y>2)
				sum++;
		}
	}
	if(m+1-v[i-1].y>2)
		sum++;
	sum+=n-v[i-1].x;
	printf("%d\n",sum);
}
        
main()
{
#if debug 	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
    int i,j;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&m,&n,&k);
		int p=0;
        for(i=0;i<k;i++)
        {
			int t1,t2;
            scanf("%d%d",&t1,&t2);
//			if(t1<=m&&t2<=n&&t1>=1&&t2>=1)
//			{
				v[p].x=t2;
				v[p].y=t1;
				p++;
//			}
        }
		k=p;
        solve();
    }

#if debug
	fclose(stdin);
	fclose(stdout);
#endif
	return 1;
}