令 $f[i][j]$ 表示之前一直往下,下一步开始往右走,之前走法的数量

令 $g[i][j]$ 表示之前一直往右,下一步开始往下走,之前走法的数量

们可以预处理出从 $(i,j)$ 开始一直往下(右)走,最多走到哪里会推不动箱子

于是转移的形式为 $f[i][j]​$ 加到 $g[i][j + 1], g[i][j + 2]\cdots g[i][pos]​$ 的转移类似

转移时间复杂度 $O(n^3)​$，转移只有区间加，可以很快优化到$O(n^2)​$

#include<bits/stdc++.h>
using namespace std;
const int maxn=2010,mod=1000000007;
inline void Add(int &a,int b){a=a+b>=mod?a+b-mod:a+b;}
int n,m,cntx[maxn][maxn],cnty[maxn][maxn],f[maxn][maxn],g[maxn][maxn];
int main()
{
	scanf("%d%d",&n,&m);if(n==1&&m==1) return puts("1"),0;
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
	{
		char c=getchar();while(c==' '||c=='\\n') c=getchar();
		if(c=='R') cntx[i][j]=cnty[i][j]=1;
	}
	for(int i=n;i;i--) 
		for(int j=m;j;j--) {
			cntx[i][j]+=cntx[i][j+1];*//从i,j点向右有多少个障碍物 *
			cnty[i][j]+=cnty[i+1][j];*//从i,j点向下有多少个障碍物 *
		}
	*//f[i][j] 表示之前是向下走,下一步向右走的方法总数*
	*//g[i][j] 表示之前是向右走,下一步向下走的方法总数 *
	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(g[i][j+1],f[i][j]);*//向下后再向右 *
		*//每次用mod-f[i][j]实际上是为了不用取mod *
		Add(g[i][m-cntx[i][j+1]+1],mod-f[i][j]);*//将i,j同一行的障碍物推到最右边,方法数+f[i][j] *
		Add(g[i][j],g[i][j-1]);
		Add(f[i+1][j],g[i][j]);
		Add(f[n-cnty[i+1][j]+1][j],mod-g[i][j]);
	}
	Add(f[n][m],g[n][m]);printf("%d\\n",f[n][m]);
	return 0;
}