啊啊啊啊啊啊啊啊啊大佬们帮帮这个菜鸡看看吧QAQAQAQAQAQAQAQAQAQAQAQAQAQAQAQAQAQAQAQAQAQAQAQAQAQ
// 轮廓线dp
#include<bits/stdc++.h>
#define int long long
#define N 33
using namespace std;
int n, m, dp[2][N][N][N];
// dp: 滚动数组
// dp[][a][b][c] 存储了第一个L在轮廓线位置a , 第二个L在轮廓线位置b , 第三个L在轮廓线位置c
// 特别的,0 是没有出现过L,m+2 为已经处理完了
char s[N][N];
signed main() {
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++)
scanf("%s",s[i]+1);
dp[1][0][0][0] = 1;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(s[i][j] == '#'){
// 障碍转移:这里没有L才能转移
for(int xa = m+2; xa >= 0; xa--) {
for(int xb = m+2; xb >= 0; xb--) {
for(int xc = m+2; xc >= 0; xc--) {
if((xa - j) * (xa - j - 1) == 0) continue;
if((xb - j) * (xb - j - 1) == 0) continue;
if((xc - j) * (xc - j - 1) == 0) continue;
dp[0][xa][xb][xc] = dp[1][xa][xb][xc];
}
}
}
}
else {
// 普通转移
for(int xa = m+2; xa >= 0; xa--) {
for(int xb = m+2; xb >= 0; xb--) {
for(int xc = m+2; xc >= 0; xc--) {
int fax = (xa == j), fay = (xa == j+1);
int fbx = (xb == j), fby = (xb == j+1);
int fcx = (xc == j), fcy = (xc == j+1);
int ds = dp[1][xa][xb][xc], Sum = fax + fay + fbx + fby + fcx + fcy;
if(Sum == 0) dp[0][xa][xb][xc] += ds;
// 如果没有L,直接转移;
if(Sum != 1) continue;
// 有多于1个L或1个L出现两次,舍去
if(fax) dp[0][xa][xb][xc] += dp[1][xa+1][xb][xc] + dp[1][0][xb][xc], dp[0][m+2][xb][xc] += ds;
if(fbx) dp[0][xa][xb][xc] += dp[1][xa][xb+1][xc] + dp[1][xa][0][xc], dp[0][xa][m+2][xc] += ds;
if(fcx) dp[0][xa][xb][xc] += dp[1][xa][xb][xc+1] + dp[1][xa][xb][0], dp[0][xa][xb][m+2] += ds;
if(fay) dp[0][xa][xb][xc] += ds + dp[1][xa-1][xb][xc];
if(fby) dp[0][xa][xb][xc] += ds + dp[1][xa][xb-1][xc];
if(fcy) dp[0][xa][xb][xc] += ds + dp[1][xa][xb][xc-1];
// 各种转移
}
}
}
}
if(j == m) continue;
for(int xa = m+2; xa >= 0; xa--)
for(int xb = m+2; xb >= 0; xb--)
for(int xc = m+2; xc >= 0; xc--)
dp[1][xa][xb][xc] = dp[0][xa][xb][xc], dp[0][xa][xb][xc] = 0;
// 数组滚动
}
for(int xa = m+2; xa >= 0; xa--) {
for(int xb = m+2; xb >= 0; xb--) {
for(int xc = m+2; xc >= 0; xc--) {
if(xa == m+1 || xb == m+1 || xc == m+1) continue;
if(xa == 1 || xb == 1 || xc == 1) continue;
int sa = xa, sb = xb, sc = xc;
if(xa != m+2 && xa != 0) sa++;
if(xb != m+2 && xb != 0) sb++;
if(xc != m+2 && xc != 0) sc++;
dp[1][sa][sb][sc] = dp[0][xa][xb][xc];
}
}
}
//轮廓在行中的转移,同一个轮廓要让L的下表增加1
for(int xa = 0; xa <= m+2; xa++)
for(int xb = 0; xb <= m+2; xb++)
for(int xc = 0; xc <= m+2; xc++)
dp[0][xa][xb][xc] = 0;
//数组滚动
}
printf("%lld\n", dp[1][m+2][m+2][m+2] / 6);
//输出:由于对于同一种方案可以有6种组合,答案要 除以6
return 0;
}
蒟蒻不希望看到无意义评论
过样例了,但只有 5 分qwq