The Happy Worm
Time Limit: 5000MS Memory Limit: 131072K
Total Submissions: 4698 Accepted: 1047
Description
The Happy Worm lives in an m*n rectangular field. There are k stones placed in certain locations of the field. (Each square of the field is either empty, or contains a stone.) Whenever the worm sleeps, it lies either horizontally or vertically, and stretches so that its length increases as much as possible. The worm will not go in a square with a stone or out of the field. The happy worm can not be shorter than 2 squares.
The question you are to answer is how many different positions this worm could be in while sleeping.
Input
The first line of the input contains a single integer t (1 <= t <= 11), the number of test cases, followed by the input data for each test case. The first line of each test case contains three integers m, n, and k (1 <= m,n,k <= 131072). The input for this test case will be followed by k lines. Each line contains two integers which specify the row and column of a stone. No stone will be given twice.
Output
There should be one line per test case containing the number of positions the happy worm can be in.
Sample Input
1
5 5 6
1 5
2 3
2 4
4 2
4 3
5 1
Sample Output
9
题意大致理解，不过在实现的过程中却又不少的疑问，希望大神们给指点一下。
#include <map>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define LL long long
#define eps 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define CRR fclose(stdin)
#define CWW fclose(stdout)
#define WW freopen("output.txt","w",stdout)
#define RR freopen("input.txt","r",stdin)
using namespace std;
const int MAX= 140010 ;
struct point
{
int x;
int y;
}a[MAX];
int sum;
bool cmp1(point a,point b)
{
if(a.x<b.x||(a.x==b.x&&a.y<b.y))
{
return true;
}
return false;
}
bool cmp2(point a,point b)
{
if(a.y<b.y||(a.y==b.y&&a.x<b.x))
{
return true;
}
return false;
}
int main()
{
int T;
int n,m,k;
scanf("%d",&T);
while(T--)
{
scanf("%d %d %d",&n,&m,&k);
for(int i=1;i<=k;i++)
{
scanf("%d %d",&a[i].x,&a[i].y);
}
sum=0;
a[0].x=1;
a[0].y=0;
a[k+1].x=n;
a[k+1].y=m+1;
sort(a+1,a+k+1,cmp1);
for(int i=1;i<=k+1;i++)
{
if(a[i].x==a[i-1].x)
{
if(a[i].y-a[i-1].y>2)
{
sum++;
}
}
else
{
sum+=(a[i].x-a[i-1].x-1);
if(m-a[i-1].y>=2)//这里为什么是>=,而不是>
{
sum++;
}
if(a[i].y-1>=2)
{
sum++;
}
}
}
a[0].x=0;
a[0].y=1;
a[k+1].x=n+1;
a[k+1].y=m;
sort(a+1,a+k+1,cmp2);
for(int i=1;i<=k+1;i++)
{
if(a[i].y==a[i-1].y)
{
if(a[i].x-a[i-1].x>2)
{
sum++;
}
}
else
{
sum+=(a[i].y-a[i-1].y-1);
if(n-a[i-1].x>=2)//这里为什么是>=,而不是>
{
sum++;
}
if(a[i].x-1>=2)
{
sum++;
}
}
}
printf("%d\n",sum);
}
return 0;
}
版权声明：本文为博主原创文章，未经博主允许不得转载。