令 $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;
}

#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];//cntx 和 maxn
  
		cnty[i][j]+=cnty[i+1][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]);//边上 (1-n/1-m/m-n/1-[m,n]) 

	Add(g[i][j+1],f[i][j]);//角上（[cntx/2]） 

	Add(g[i][m-cntx[i][j+1]+1],mod-f[i][j]);//边角交接（[1,1][1,n][n,m][1,m]） 

	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]);//1-[n,m/1,n/1,m]

return 0;

}

#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(n1&&m1) 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];//cntx 和 maxn cnty[i][j]+=cnty[i+1][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]);//边上 (1-n/1-m/m-n/1-[m,n]) Add(g[i][j+1],f[i][j]);//角上（[cntx/2]） Add(g[i][m-cntx[i][j+1]+1],mod-f[i][j]);//边角交接（[1,1][1,n][n,m][1,m]） 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]);//1-[n,m/1,n/1,m] return 0; }