题意：
戳这里查看
分析：
我们可以通过手调样例发现最后整张图会沿着一条线分为两个部分，所以我们利用这条分界线进行DP，我们设
f
[
i
]
[
j
]
[
0
]
f[i][j][0]
f[i][j][0]表示现在在第
i
i
i行第
j
j
j列的格子右下角的点，0表示该向右延展，1表示向下扩展，每次方向变化时需要除以二，因为有一个原来可放可不放的格子不得不放，情况减少了，转移的话看代码就能看懂
代码：
#include<bits/stdc++.h>
using namespace std
;
namespace zzc
{
const int maxn
= 2005;
const int mod
= 1e9+7;
const int inv2
= 500000004;
bool vis
[maxn
][maxn
];
int f
[maxn
][maxn
][2];
int n
,cnt
=1;
char ch
[maxn
];
void work()
{
scanf("%d",&n
);
for(int i
=1;i
<=n
;i
++)
{
scanf("%s",ch
+1);
for(int j
=1;j
<=n
;j
++)
{
if(ch
[j
]=='.')
{
vis
[i
][j
]=true;
cnt
=cnt
*2%mod
;
}
}
}
f
[1][0][1]=cnt
;
f
[0][1][0]=cnt
;
for(int i
=0;i
<=n
;i
++)
{
for(int j
=0;j
<=n
;j
++)
{
if(f
[i
][j
][0])
{
f
[i
][j
+1][0]=(f
[i
][j
][0]+f
[i
][j
+1][0])%mod
;
if(vis
[i
+1][j
]) f
[i
+1][j
][1]=(f
[i
+1][j
][1]+(long long)f
[i
][j
][0]*inv2
%mod
)%mod
;
}
if(f
[i
][j
][1])
{
f
[i
+1][j
][1]=(f
[i
+1][j
][1]+f
[i
][j
][1])%mod
;
if(vis
[i
][j
+1]) f
[i
][j
+1][0]=(f
[i
][j
+1][0]+(long long)f
[i
][j
][1]*inv2
%mod
)%mod
;
}
}
}
printf("%d\n",(f
[n
][n
][0]+f
[n
][n
][1])%mod
);
}
}
int main()
{
zzc
::work();
return 0;
}
