算法1

轮廓线DP

usaco打卡

C++ 代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 2010;
const LL MOD = 1e9 + 7;
int n;
char g[N][N];
int f[N][N][2];
int sl[N][N], su[N][N];
int tk[N];

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i) scanf("%s", g[i] + 1);
    for(int i = 1; i <= n; ++ i)
        for(int j = 1; j <= n; ++ j)
        {
            su[i][j] = su[i - 1][j] + (g[i][j] == '.');
            sl[i][j] = sl[i][j - 1] + (g[i][j] == '.');
        }
    tk[0] = 1;
    for(int i = 1; i <= 2000; ++ i) tk[i] = ((LL)tk[i - 1] * 2ll) % MOD;
    for(int i = 1; i <= n; ++ i) f[0][i][0] = 1ll;
    for(int i = 1; i <= n; ++ i) f[i][0][1] = 1ll;
    for(int i = 0; i <= n; ++ i)    
        for(int j = 0; j <= n; ++ j)
        {
            if(j)
            {
                if(i) (f[i][j + 1][0] += 
                (((LL)f[i][j][0] * tk[su[i][j + 1]]) % MOD)) %= MOD;
                if(g[i + 1][j] != 'W') 
                (f[i + 1][j][1] +=
                (((LL)f[i][j][0] * tk[sl[i + 1][j - 1]]) % MOD)) %= MOD;
            }
            if(i)
            {
                if(j) (f[i + 1][j][1] += 
                (((LL)f[i][j][1] * tk[sl[i + 1][j]]) % MOD)) %= MOD;
                if(g[i][j + 1] != 'W') (f[i][j + 1][0] += 
                (((LL)f[i][j][1] * tk[su[i - 1][j + 1]]) % MOD)) %= MOD;
            }
        }
    printf("%lld", (f[n][n][0] + f[n][n][1]) % MOD);
    return 0;
}