比较简单的插头 DP 题。
考虑把一个 L 型的东西看做一条拐了一次弯的路径，可以在插头上区分插头所在路径是否已经拐过弯。
设 \(1\) 表示未拐弯，\(2\) 表示已拐弯。
按照插头类型分类讨论 \((i,j)\) 的决策：
无左插头和上插头。
- 以 \((i,j)\) 为一个 L 型的拐点，并令这个 L 型向右方和下方延伸。即在当前格子添加类型为 \(2\) 的右插头和下插头各一个。
- 以 \((i,j)\) 为一个 L 型的一端。即在当前格子添加类型为 \(1\) 的右插头或下插头一个。
上插头类型 \(1\)，无左插头。
- 一个由上而下延伸的 L 型经过 \((i,j)\)。即在当前格子添加类型为 \(1\) 的下插头一个。
- 以 \((i,j)\) 为一个由上而下延伸的 L 型的拐点，并令这个 L 型从此向右延伸。即在当前格子添加类型为 \(2\) 的右插头一个。
左插头类型 \(1\)，无上插头。 类比上述情况。
上插头类型 \(2\)，无左插头。
- 一个由上而下延伸的 L 型经过 \((i,j)\)。即在当前格子添加类型为 \(2\) 的下插头一个。
- 以 \((i,j)\) 为一个由上而下延伸的 L 型的一端。即不在当前格子添加任何插头。
左插头类型 \(2\)，无上插头。 类比上述情况。
左插头、上插头均为类型 \(1\)。 以 \((i,j)\) 为一个 L 型的拐点。即不在当前格子添加任何插头。
注意不添加插头的 \(3\) 种情况需要统计答案（当且仅当该格子是最后一个没有障碍的格子）。
代码： 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
using namespace std;
const int N = 100;
const int MX = 1e6;
const int hash_mod = 70921;
const int mod = 20110520;
int n,m,a[N + 5][N + 5],edx,edy;
int f[2][MX + 5],ans;
int key[2][MX + 5],tot[2],pre[2][MX + 5],first[2][hash_mod + 5];
inline void trans(int cur,int s,int v)
{
int h = s % hash_mod;
for(register int i = first[cur][h];i;i = pre[cur][i])
if(key[cur][i] == s)
{
f[cur][i] = (f[cur][i] + v) % mod;
return ;
}
key[cur][++tot[cur]] = s,f[cur][tot[cur]] = v,pre[cur][tot[cur]] = first[cur][h],first[cur][h] = tot[cur];
}
int main()
{
scanf("%d%d",&n,&m);
char ch;
for(register int i = 1;i <= n;++i)
for(register int j = 1;j <= m;++j)
scanf(" %c",&ch),((n < m ? a[j][i] : a[i][j]) = ch == '_') && (edx = i,edy = j);
n < m && (swap(n,m),swap(edx,edy),1);
trans(0,0,1);
for(register int i = 1,cur = 0;i <= n;++i)
{
for(register int j = 1;j <= tot[cur];++j)
key[cur][j] <<= 2;
for(register int j = 1;j <= m;++j,cur ^= 1)
{
memset(first[cur ^ 1],0,sizeof first[cur ^ 1]),tot[cur ^ 1] = 0;
for(register int k = 1;k <= tot[cur];++k)
{
int s = key[cur][k],up = (s >> bits(j + 1)) & 3,left = (s >> bits(j)) & 3;
int v = f[cur][k];
if(!a[i][j])
!up && !left && (trans(cur ^ 1,s,v),1);
else if(!up && !left)
a[i + 1][j] && a[i][j + 1] && (trans(cur ^ 1,s + (2 << bits(j)) + (2 << bits(j + 1)),v),1),
a[i + 1][j] && (trans(cur ^ 1,s + (1 << bits(j)),v),1),
a[i][j + 1] && (trans(cur ^ 1,s + (1 << bits(j + 1)),v),1);
else if(up == 1 && !left)
a[i + 1][j] && (trans(cur ^ 1,s - (1 << bits(j + 1)) + (1 << bits(j)),v),1),
a[i][j + 1] && (trans(cur ^ 1,s + (1 << bits(j + 1)),v),1);
else if(!up && left == 1)
a[i][j + 1] && (trans(cur ^ 1,s - (1 << bits(j)) + (1 << bits(j + 1)),v),1),
a[i + 1][j] && (trans(cur ^ 1,s + (1 << bits(j)),v),1);
else if(up == 2 && !left)
a[i + 1][j] && (trans(cur ^ 1,s - (2 << bits(j + 1)) + (2 << bits(j)),v),1),
trans(cur ^ 1,s - (2 << bits(j + 1)),v),
i == edx && j == edy && (ans = (ans + v) % mod);
else if(!up && left == 2)
a[i][j + 1] && (trans(cur ^ 1,s - (2 << bits(j)) + (2 << bits(j + 1)),v),1),
trans(cur ^ 1,s - (2 << bits(j)),v),
i == edx && j == edy && (ans = (ans + v) % mod);
else if(up == 1 && left == 1)
trans(cur ^ 1,s - (1 << bits(j)) - (1 << bits(j + 1)),v),
i == edx && j == edy && (ans = (ans + v) % mod);
}
}
}
printf("%d\n",ans);
}