每日一水第38弹(WF 2010C)

给一个m*n的网格,有一些墙,问你有多少的点无法到达右上角,只能往右或往上移动。

离散化之后dp,把所有等价的空白格子当成一个格子来考虑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
using namespace std;
const int N = 4010;
 
map<int, int> mx, my;
int dp[N][N];
int x[N], y[N];
struct Line
{
    int s, e, h;
    void in() {
        scanf("%d%d%d%d", &s, &h, &e, &h);
    }
}line[N];
int main()
{
    int m, n, w, ca = 1;
    while(scanf("%d%d%d", &m, &n, &w) == 3) {
        if(!m && !n && !w) {
            break;
        }
        mx.clear(); my.clear();
        for(int i = 0; i < w; i++) {
            line[i].in();
            mx[line[i].s] = 1;
            mx[line[i].s - 1] = 1;
            mx[line[i].e + 1] = 1;
            mx[line[i].e] = 1;
 
            my[line[i].h] = 1;
            my[line[i].h - 1] = 1;
            my[line[i].h + 1] = 1;
        }
        mx[0] = mx[n - 1] = mx[n] = 1;
        my[0] = my[m - 1] = my[m] = 1;
        int nn = 0;
        for(auto it: mx) {
            x[nn] = it.first;
            mx[it.first] = nn++;
        }
        int mm = 0;
        for(auto it: my) {
            y[mm] = it.first;
            my[it.first] = mm++;
        }
        for(int i = 0; i <= nn; i++) {
            for(int j = 0; j <= mm; j++) {
                dp[i][j] = 0;
            }
        }
        nn = mx[n], mm = my[m];
        dp[nn - 1][mm - 1] = 1;
        for(int i = 0; i < w; i++) {
            int s = line[i].s, e = line[i].e, h = line[i].h;
            s = mx[s], e = mx[e], h = my[h];
            for(int j = s; j <= e; j++) {
                dp[j][h] = -1;
            }
        }
        for(int j = mm - 1; j >= 0; j--) {
            for(int i = nn - 1; i >= 0; i--) {
                if(dp[i][j] != -1) {
                    if(dp[i + 1][j] > 0 ¦¦ dp[i][j + 1] > 0) {
                        dp[i][j]  = 1;
                    }
                }
            }
        }
        long long ret = 0;
        for(int i = 0; i < nn; i++) {
            for(int j = 0; j < mm; j++) if(dp[i][j] == 0){
                if(x[i] >= 0 && x[i] <= n - 1 && y[j] >= 0 && y[j] <= m - 1)
                ret += 1LL * (x[i + 1] - x[i]) * (y[j + 1] - y[j]);
            }
        }
        printf("Case %d: %lld\n", ca++, ret);
    }
    return 0;
}

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注