另解，不过也是 \(dp\) 。
一个小套路，关于平方我们可以考虑他的组合意义。
假如一条路径上有三个 \(YY\)
那么他的贡献是 \((1+1+1)^2=(1+1+1)(1+1+1)\)
相当于是从左右两边括号里各选一个 \(1\) 。
所以实际上我们的贡献可以看成从 \((1,1)\to (n,n)\) 路径上中所有 \(YY\) 中任选两个 \(YY\) 的方案数（可以选同一个，而且算的是有序对的个数）。
所以我们记状态 \(f_{i,j,0/1/2,0/1/2}\) 表示到了 \(i,j\) 这个位置，路径上的 \(YY\) 选了 \(0/1/2\) 个，然后目前连续的 \(Y\) 的个数是 \(0/1/2\) 个。
时间复杂度 \(O(9n^2)\)
点击查看代码
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int MAXN=2010,P=998244353;
int n,m;
int f[MAXN][MAXN][3][3];
char ch[MAXN][MAXN];
LL add(LL x,LL y) {
return (x+y>=P?x+y-P:x+y);
}
int main () {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) {
scanf("%s",ch[i]+1);
}
f[1][1][0][(ch[1][1]=='Y')]=1;
for(int i=1;i<=n;++i) {
for(int j=1;j<=m;++j) {
if(i==1&&j==1) continue;
for(int q=0;q<=2;++q) {
for(int w=0;w<=2;++w) {
f[i][j][q][w]=add(f[i][j][q][w],f[i-1][j][q][w]);
f[i][j][q][w]=add(f[i][j][q][w],f[i][j-1][q][w]);
}
}
if(ch[i][j]=='X') {
for(int q=0;q<=2;++q) {
f[i][j][q][0]=add(f[i][j][q][0],f[i][j][q][1]);
f[i][j][q][0]=add(f[i][j][q][0],f[i][j][q][2]);
f[i][j][q][1]=f[i][j][q][2]=0;
}
}
else {
for(int q=0;q<=2;++q) {
f[i][j][q][2]=add(f[i][j][q][2],f[i][j][q][1]);
f[i][j][q][1]=f[i][j][q][0];
f[i][j][q][0]=0;
}
f[i][j][2][2]=add(f[i][j][2][2],add(f[i][j][1][2]*2%P,f[i][j][0][2]));
f[i][j][1][2]=add(f[i][j][1][2],f[i][j][0][2]);
}
}
}
printf("%lld\n",add(f[n][m][2][0],add(f[n][m][2][1],f[n][m][2][2])));
return 0;
}