题意

题目链接。

$n\times m$ 的场地上存在一些箱子，碰到了就会被推动，不可以使任何箱子被推出场地。求从 $(1,1)$ 走到 $(n,m)$ 的方案数。

解析

发现该问题类似于过河卒，考虑 dp。由于向右和向下移动所涉及的箱子不同，且如果越过了箱子就一定不会再次推到（不能往回走），考虑如下设置状态：

记 $f_{i,j}$ 为从上方走到 $(i,j)$ 的所有方案数，$g_{i,j}$ 为从左方走到 $(i,j)$ 的所有方案数。在不考虑箱子的情况下，显然有：$f_{i,j}=f_{i-1,j}+g_{i-1,j}$ 和 $g_{i,j}=g_{i,j-1}+f_{i,j-1}$。

容斥思想下，我们再考虑减去不合法的方案数。我们发现除了第一排和第一列以外，其他行列都可以看作有上一行某处走下来再向右走或从左一列走过来再向下走。因此我们可以抽象出第 $0$ 行和第 $0$ 列，并赋予初值 $f_{1,1}=g_{1,1}=1$，为防止答案重复统计，同时也赋予初值 $f_{2,1}=g_{1,2}=-1$，容易判断这是正确的。

在此前提下，以除去不合法的向右走方案数为例。我们发现如果往下走到 $(i,j)$，由于 $(i,j)$ 及其左边的箱子都不会被推到，我们只需要判断一直往右走到哪里不合法就可以了。类似于前缀和地定义 $r_{i,j}$ 为 $(i,j)$ 及其右边（同一行）的箱子数总和。则除去从上方走到 $(i,j)$ 再往右走的不合法方案等价于将 $g_{i,m-r_{i,j+1}+1}$ 减去 $f_{i,j}$，另一个同理，详见代码。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+5;
const int mod=1e9+7;
int n,m;
char ma[N][N];
int f[N][N];//向下走
int g[N][N];//向右走
int r[N][N],d[N][N];//石头数
inline void add(int &a,int b){
    a=a+b>=mod?a+b-mod:a+b;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%s",ma[i]+1);
    if(n==1&&m==1){printf("1\n");return 0;}//特判
    for(int i=n;i>=1;i--){
        for(int j=m;j>=1;j--){
            if(ma[i][j]=='R') r[i][j]=d[i][j]=1;
            r[i][j]+=r[i][j+1];d[i][j]+=d[i+1][j];
        }
    }//预处理 r,d 数组
    f[1][1]=g[1][1]=1;
    f[2][1]=g[1][2]=-1;//这么做是为了防止第一行和第一列有方案未删除或重复
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            add(f[i][j],f[i-1][j]);add(f[i][j],g[i-1][j]);
            add(g[i][m-r[i][j+1]+1],mod-f[i][j]);
            add(g[i][j],g[i][j-1]);add(g[i][j],f[i][j-1]);
            add(f[n-d[i+1][j]+1][j],mod-g[i][j]);
        }
    }
    printf("%d\n",(f[n][m]+g[n][m])%mod);
    return 0;
}