poj 1974

题意：有一只蠕虫居住在一个m*n大小的网格中,在网格的某些位置放置了k块石头,当蠕虫睡觉时,它在水平方向或垂直方向上躺着,把身体尽可能伸展开来,蠕虫的身体既不能进入到放有石块的方格中,也不能伸出网格外,而且蠕虫的长度不会短于2个方格的大小.现在给定一网格,要求计算蠕虫可以在多少个不同的位置可以躺下睡觉.

题目中有两点需要注意:
        1>当蠕虫睡觉时,它在水平方向或垂直方向上躺着,把身体尽可能伸展开来.
        2>蠕虫的长度不会短于2个方格的大小.

 

思路：先找出在有石块的行方向上可以睡觉的位置及在有石块的列方向上可以睡觉的位置,然后再找出那些没有石块的行和列位置上可以睡觉的位置。

具体代码如下：

#include<iostream>
#include<string>
#include<cstdlib>
#include<algorithm>
using namespace std;

struct Point
{
       int u;
       int v;
}p[132000];

int r[132000];
int c[132000];

bool cmpx(const Point & p1,const Point & p2)                       //先按x坐标升序排序,x坐标相等时,再按y坐标升序排序
{
     if(p1.u!=p2.u)
        return p1.u<p2.u;
     else
        return p1.v<p2.v;
}

bool cmpy(const Point & p1,const Point & p2)                     //先按y坐标升序排序,y坐标相等时,再按x坐标升序排序
{
      if(p1.v!=p2.v)
        return p1.v<p2.v;
     else
        return p1.u<p2.u;
}

int main()
{
    int i,k,t,m,n,x,y,ans;
    scanf("%d",&t);
    while(t--)
    {
         scanf("%d%d%d",&m,&n,&k);
         if(k==0)                                                                      //k=0时需要特殊处理
         {
              printf("%d\n",m+n);
              continue;
         }
         ans=0;
         memset(r,0,sizeof(r));
         memset(c,0,sizeof(c));
         for(i=0;i<k;i++)
         {
              scanf("%d%d",&p[i].u,&p[i].v);
              r[p[i].u]=1;                                                           //标记石块在哪一行和那一列
              c[p[i].v]=1;
         }
         sort(p,p+k,cmpx);
         x=p[0].u;
         y=p[0].v;
         if(y>2)
           ans++;
         for(i=1;i<k;i++)
         {
              if(p[i].u==x)
              {
                     if(p[i].v-y>2)
                        ans++;
                     y=p[i].v;
              }
              else
              {
                     if(p[i].v>2)
                        ans++;
                     if(n-y+1>2)                     //下标为i的石块的横坐标和i-1不同,则应对i-1的竖坐标进行判断,下同
                        ans++;
                     x=p[i].u;
                     y=p[i].v;
              }
         }
         if(n-y+1>2)
            ans++;
         sort(p,p+k,cmpy);
         x=p[0].u;
         y=p[0].v;
         if(x>2)
            ans++;
         for(i=1;i<k;i++)
         {
              if(p[i].v==y)
              {
                     if(p[i].u-x>2)
                        ans++;
                     x=p[i].u;
              }
              else
              {
                     if(p[i].u>2)
                       ans++;
                     if(m-x+1>2)
                       ans++;
                     x=p[i].u;
                     y=p[i].v;
              }
         }
         if(m-x+1>2)
            ans++;
         for(i=1;i<=m;i++)                                                   //判断那些行没有石块
            if(r[i]==0)
               ans++;
         for(i=1;i<=n;i++)
            if(c[i]==0)
               ans++;
         printf("%d\n",ans);
    }
    system("pause");
    return 0;

}