思想很单纯-> dp
Code:
代码解释：
dp[i][j] += ans[1][i-1][j];///竖着过来 dp[i][j] %= mod; dp[i][j] += ans[2][i][j-1];///横着过来 dp[i][j] %= mod; dp[i][j] += ans[3][i-1][j-1];///斜着过来
dp加上之后，注意进行取模
然后再更新这一个节点的计数（ans）
ans[1][i][j] = (ans[1][i-1][j] + dp[i][j]) % mod; ans[2][i][j] = (ans[2][i][j-1] + dp[i][j]) % mod; ans[3][i][j] = (ans[3][i-1][j-1] + dp[i][j]) % mod;
char s[2008][2008]; ll ans[4][2008][2008]; ll dp[2008][2008]; int main() { int n = read,m = read; dp[1][1] = 1; for(int i = 1;i <= n;i++) cin >> s[i] + 1; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(s[i][j] == '#'){ ans[1][i][j] = 0; ans[2][i][j] = 0; ans[3][i][j] = 0; continue; } dp[i][j] += ans[1][i-1][j]; dp[i][j] %= mod; dp[i][j] += ans[2][i][j-1]; dp[i][j] %= mod; dp[i][j] += ans[3][i-1][j-1]; dp[i][j] %= mod; ans[1][i][j] = (ans[1][i-1][j] + dp[i][j]) % mod; ans[2][i][j] = (ans[2][i][j-1] + dp[i][j]) % mod; ans[3][i][j] = (ans[3][i-1][j-1] + dp[i][j]) % mod; } } cout << dp[n][m] <<endl; return 0; }
