1126: [POI2008]Uci

https://lydsy.com/JudgeOnline/problem.php?id=1126

分析：

　　dp。状态很妙，就是有点难写。

　　能走的是一个矩形。首先考虑从x,y只能往左拐，到n,1的方案数。矩形是增加的。然后f[u][l][d][r][0/1/2/3]表示上边界u，左边界l，下边界d，右边界r的矩形，在左上角/右下角/左下角/左上角的方案数。

　　然后考虑这个从这个点可以沿着原来的方向走一步。或者拐弯（拐弯后直接到下一个角上，比如在右下角，拐弯后到右上角）。

　　初始值设为可以到x,y的，所有的点，尽管这些状态是不存在的。

　　空间开不下，把第一维滚动掉。

　　（开始想的的“推”的dp，这样的话初始值就比较方便了，但是就无法滚动第一维了）

代码：

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<cmath>
 6 #include<cctype>
 7 #include<set>
 8 #include<queue>
 9 #include<vector>
10 #include<map>
11 using namespace std;
12 typedef long long LL;
13 
14 inline int read() {
15     int y=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
16     for(;isdigit(ch);ch=getchar())y=y*10+ch-'0';return y*f;
17 }
18 
19 const int N = 105;
20 
21 int sr[N][N], sc[N][N], f[2][N][N][N][4];
22 char s[N];
23 int mod;
24 
25 inline void add(int &x,int y) {
26     x += y; if (x >= mod) x -= mod;
27 }
28 
29 int main() {
30     int n = read(), m = read();mod = read();int x = read(), y = read();
31     for (int i = 1; i <= n; ++i) {
32         scanf("%s", s + 1);
33         for (int j = 1; j <= m; ++j) {
34             sr[i][j] = sr[i][j - 1] + (s[j] == '+');
35             sc[i][j] = sc[i - 1][j] + (s[j] == '+');
36         } 
37     }
38     int ans = 0;
39     f[1][x][y][x][0] = 1;
40     f[0][x][y][x - 1][1] = 1;
41     f[0][x][y - 1][x][2] = 1;
42     f[0][x + 1][y][x][3] = 1;
43 
44     for (int u = y, now = 0; u >= 1; --u, now ^= 1) {
45         if (u != y) memset(f[now], 0, sizeof(f[now]));
46         for (int l = x; l >= 1; --l) 
47             for (int d = y; d <= n; ++d) 
48                 for (int r = x; r <= m; ++r) {
49                     if (sc[d][r] - sc[u - 1][r] == d - u + 1) {
50                         f[now][l][d][r][0] = f[now][l][d][r - 1][1];
51                         if (u < d) add(f[now][l][d][r][0], f[!now][l][d][r][0]);
52                     }
53                     if (sr[d][r] - sr[d][l - 1] == r - l + 1) {
54                         f[now][l][d][r][1] = f[now][l][d - 1][r][2];
55                         if (l < r) add(f[now][l][d][r][1], f[now][l][d][r - 1][1]);
56                     }
57                     if (sc[d][l] - sc[u - 1][l] == d - u + 1) {
58                         f[now][l][d][r][2] = f[now][l + 1][d][r][3];
59                         if (u < d) add(f[now][l][d][r][2], f[now][l][d - 1][r][2]);
60                     }
61                     if (sr[u][r] - sr[u][l - 1] == r - l + 1) {
62                         f[now][l][d][r][3] = f[!now][l][d][r][0];
63                         if (l < r) add(f[now][l][d][r][3], f[now][l + 1][d][r][3]);
64                     }
65                     if (u == y && d == y && l == x && r == x) {
66                         f[1][x][y][x][0] = 0;
67                         f[0][x][y][x - 1][1] = 0;
68                         f[0][x][y - 1][x][2] = 0;
69                         f[0][x + 1][y][x][3] = 0;
70                     }
71                     if (l == 1 && d == n) add(ans, f[now][l][d][r][2]);
72                 }
73     }
74     cout << ans;
75     return 0;
76 }