The Happy Worm 分类： POJ ...-白红宇

The Happy Worm 分类： POJ ...

阅读量：4696 次

发布时间：2019-06-09

本文共 2279 字，大约阅读时间需要 7 分钟。

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

5 5 6

1 5

2 3

2 4

4 2

4 3

5 1

Sample Output

题意大致理解，不过在实现的过程中却又不少的疑问，希望大神们给指点一下。

#include #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #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
                
                 
                  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;}

转载于:https://www.cnblogs.com/juechen/p/4721934.html

你可能感兴趣的文章