效率比较低但码量也较少的方法。
本题要求有三个$L$形,那么我们的轮廓线上最多有三个插头,轮廓线状态数上界估计为$6 \times C_{31}^3$约为$3$万,时间复杂度预估为$30000 \times 900$,大概可以通过,我们用$1、2、3$分别表示第$1、2、3$个$L$的插头,用$0$表示没有插头,四进制状压,每格占两位,一共$31$格,可以用$64$位整数存下。
考虑状态合法的条件是什么,首先需要生成$3$个插头,其次题目要求$L$必须拐弯,于是每个插头都拐过弯状态就必然合法,不难想到在状态里压入两个参数$c$和$t$记录插头生成个数和拐弯次数,下面考虑状态转移。
$u$和$l$分别表示上、左插头编号,$r$和$d$表示右、下是否是合法块。
-
$Case1\;\;$ 当前格不能摆
轮廓线状态不变,直接转移。
-
$Case2\;\;$ $ l\;and\;u$
不合法,不转移。
-
$Case3\;\;$ $ l\;and\;!u$
1.左插头截断。 2.若r则左插头可以延续。
-
$Case4\;\;$ $ !l\;and\;u$
1.上插头转弯(t++) 2.若d则上插头可以延续,注意上插头不能截断。
-
$Case5\;\;$ $ !l\;and\;!u$
1.不摆,轮廓线不变。 2.若c<3,则可以生成新插头,c++。
注意每行结束要滚动,最后合法的状态即为$c=3$且$t=3$。
#include <iostream>
#include <cstring>
#pragma GCC optimize(2)
using namespace std;
using i64 = long long;
const int N = 35000, M = 70007;
const int offset = 2, mask = 3;
int g[32][32];
int n, m;
struct Hash_Table {
int h[M], ne[N], idx;
i64 state[N], val[N];
int cnt[N], turn[N];
void init() {
memset(h, -1, sizeof h);
idx = 0;
}
void push(i64 s, i64 v, int c, int t) {
int x = s % M;
for (int i = h[x]; ~i; i = ne[i])
if (state[i] == s && cnt[i] == c && turn[i] == t)
return val[i] += v, void();
state[idx] = s, val[idx] = v, turn[idx] = t, cnt[idx] = c;
ne[idx] = h[x], h[x] = idx++;
}
void roll() {
for (int i = 0; i < idx; i++) state[i] <<= offset;
}
} h[2], *h0, *h1;
void add(i64 s, i64 v, int c, int t) {
h1->push(s, v, c, t);
}
i64 set(int x, int y) {
return y * (1ll << (x * offset));
}
int get(i64 x, int y) {
return x >> (y * offset) & mask;
}
void trans(int i, int j) {
swap(h1, h0);
h1->init();
for (int k = 0; k < h0->idx; k++) {
i64 s = h0->state[k], v = h0->val[k];
int c = h0->cnt[k], t = h0->turn[k];
int l = get(s, j), u = get(s, j + 1);
int d = g[i + 1][j], r = g[i][j + 1];
if (l && u) continue;
if (!g[i][j]) add(s, v, c, t);
else if (u) {
if (d) add(s + set(j, u) - set(j + 1, u), v, c, t);
if (r) add(s, v, c, t + 1);
}
else if (l) {
if (r) add(s - set(j, l) + set(j + 1, l), v, c, t);
add(s - set(j, l), v, c, t);
}
else {
if (c < 3 && d) add(s + set(j, c + 1), v, c + 1, t);
add(s, v, c, t);
}
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
char c;
cin >> c;
if (c == '.') g[i][j] = 1;
}
}
h0 = h, h1 = h + 1;
h1->init();
add(0, 1, 0, 0);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) trans(i, j);
h1->roll();
}
i64 res = 0;
for (int i = 0; i < h1->idx; i++)
if (h1->cnt[i] == 3 && h1->turn[i] == 3)
res += h1->val[i];
cout << res << '\n';
return 0;
}