排序+HASH，地址：http://acm.pku.edu.cn/JudgeOnline/problem?id=1974
#include <stdio.h>
#include <stdlib.h>

const int MAX = 131075;

typedef struct
{
    int x;
    int y;
    int next;
}point;


point p[MAX];//多少个有石头的结点
int now;
struct
{
    int next;//下一个
    int last;//最后一个的位置
}hash[MAX];

void init ( int len )
{

    now = 0;
    for ( int i=0; i<len; i++ )
    {
        hash[i].next = -1;
        hash[i].last = -1;
    }
}

void add ( point *node )
{

    p[now].next = -1;
    p[now].x = node->x;
    p[now].y = node->y;

    int head = node->x;
    if ( hash[head].next == -1 )
    {
        hash[head].next = now;
    }
    else
    {
        p[ hash[head].last ].next = now;
    }
    hash[head].last = now ++;
}

point num[MAX];

int cmpx ( const void *a, const void *b )//以X为主要排序策略
{

    int ans = ( ( point * )a )->x - ( ( point * )b )->x;
    if ( ! ans )
    {
        ans = ( ( point * )a )->y - ( ( point * )b )->y;
    }

    return ans;
}

int cmpy ( const void *a, const void *b )//以Y为主要排序策略
{

    int ans = ( ( point * )a )->y - ( ( point * )b )->y;
    if ( ! ans )
    {
        ans = ( ( point * )a )->x - ( ( point * )b )->x;
    }

    return ans;
}


int main ()
{

    int t;
    int n, m, k;
    int i;

    scanf ( "%d", &t );
    while ( t -- )
    {
        scanf ( "%d%d%d", &m, &n, &k );
        for ( i=0; i<k; i++ )
        {
            scanf ( "%d%d", &num[i].x, &num[i].y );
            num[i].x --;
            num[i].y --;
        }

        int count = 0;
        qsort ( num, k, sizeof ( point ), cmpy );
        init ( n );
        for ( i=0; i<k; i++ )
        {
            point node;
            node.x = num[i].y;
            node.y = num[i].x;
            add ( &node );
        }
        for ( i=0; i<n; i++ )
        {
            if ( hash[i].next == -1 )
            {
                count ++;
            }
            else
            {
                int temp = 0;
                int j = hash[i].next;
                if ( p[j].y - 0 > 1 )
                {
                    count ++;
                }
                for ( j=hash[i].next; p[j].next!=-1; j=p[j].next )
                {
                    int nextj = p[j].next;
                    if ( p[nextj].y - p[j].y > 2 )
                    {
                        count ++;
                    }
                }
                if ( m-1 - p[j].y > 1 )
                {
                    count ++;
                }
            }
        }

        qsort ( num, k, sizeof ( point ), cmpx );
        init ( m );
        for ( i=0; i<k; i++ )
        {
            add ( &num[i] );
        }
        for ( i=0; i<m; i++ )
        {
            if ( hash[i].next == -1 )
            {
                count ++;
            }
            else
            {
                int temp = 0;
                int j = hash[i].next;
                if ( p[j].y - 0 > 1 )
                {
                    count ++;
                }
                for ( j=hash[i].next; p[j].next!=-1; j=p[j].next )
                {
                    int nextj = p[j].next;
                    if ( p[nextj].y - p[j].y > 2 )
                    {
                        count ++;
                    }
                }
                if ( n-1 - p[j].y > 1 )
                {
                    count ++;
                }
            }
        }

        printf ( "%d\n", count );
    }
    return 0;
}