POJ 1974 - The Happy Worm

http://poj.org/problem?id=1974

概要

\(m \times n\) のグリッド上に \(k\) 個の石が置かれている。 The Happy Worm は水平方向あるいは垂直方向に、石や壁が無い限りできるだけ体を長くして寝る。 ただし The Happy Worm は2マスよりも小さい領域には寝ることはない。

このとき、The Happy Worm が寝る位置は何通りあるか答える。

制約

• \(1 \le m, n, k \le 131072\)

解法

水平方向と垂直方向の両方に対して、石の間隔が2マス以上離れている箇所の数を数える。 壁のある位置にダミーの石があるとしてやるとやりやすい。

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int countup(pair<int,int> *first, pair<int,int> *last)
 6 {
 7   sort(first, last);
 8   int n = 0;
 9   int r = first->first;
10   int c = first->second;
11   for (pair<int,int> *it = first+1; it != last; ++it) {
12     if (it->first == r && it->second - c > 2) {
13       ++n;
14     }
15     r = it->first;
16     c = it->second;
17   }
18   return n;
19 }
20 
21 int main()
22 {
23   int T;
24   scanf("%d", &T);
25   while (T-- > 0) {
26     int M, N, K;
27     scanf("%d %d %d", &M, &N, &K);
28     static pair<int,int> a[700000];
29     for (int i = 0; i < K; i++) {
30       scanf("%d %d", &a[i].first, &a[i].second);
31     }
32     pair<int,int> *p = a+K;
33     for (int i = 1; i <= M; i++) {
34       p->first = i;
35       p->second = 0;
36       ++p;
37       p->first = i;
38       p->second = N+1;
39       ++p;
40     }
41     for (int i = 1; i <= N; i++) {
42       p->first = 0;
43       p->second = i;
44       ++p;
45       p->first = M+1;
46       p->second = i;
47       ++p;
48     }
49     int ans = countup(a, p);
50     for (pair<int,int> *it = a; it != p; ++it) {
51       swap(it->first, it->second);
52     }
53     ans += countup(a, p);
54     printf("%d\n", ans);
55   }
56   return 0;
57 }