Bronze 确实都是简单题,我这种撒币都能做得来
Method 考虑一个 dp[x][y][转弯次数][方向] 代表在这些条件下的合法路径数
转弯次数:路径上共有多少转弯处 ($0$ ~ $k$,在此题中最高为 $3$) 方向:上一个位置向当前位置前进的方向 ($0/1$) $0$ 为右,$1$ 为下 当上一个状态的方向与当前状态的方向不同时将转弯次数 $+1$ 当前位置有障碍物时设为 $0$ 同时这种方法需要进一步优化
将每一个在顶边或左边的块设为 $1$ 条 $0$ 次转弯的路径,$0$ 条其他转弯次数的路径
当顶边或左边中某一块为障碍物,将其右侧(顶边)或底部(左边)的块设为无路径可达
Code int T, n, k, ans; int dp[100][100][4][2]; int main() { read(T); while(T--) { ans = 0; read(n, k); for(int i = 1; i <= n; ++i) dp[1][i][0][0] = 1; for(int i = 1; i <= n; ++i) dp[i][1][0][1] = 1; for(int i = 1; i <= n; ++i) { for(int j = 1; j <= n; ++j) { char c = getchar(); if(i == 1 || j == 1) { if(c == 'H') if(i == 1) for(int l = j; l <= n; ++l) dp[i][l][0][0] = dp[i][l][0][1] = 0; else if(j = 1) for(int l = i; l <= n; ++l) dp[l][j][0][0] = dp[l][j][0][1] = 0; continue; } for(int l = 0; l <= k; ++l) if(!l) { dp[i][j][l][0] = dp[i][j - 1][l][0]; dp[i][j][l][1] = dp[i - 1][j][l][1]; } else if(c == '.') { dp[i][j][l][0] = dp[i][j - 1][l - 1][1] + dp[i][j - 1][l][0]; dp[i][j][l][1] = dp[i - 1][j][l - 1][0] + dp[i - 1][j][l][1]; } else if(c == 'H') dp[i][j][l][0] = dp[i][j][l][1] = 0; } getchar(); } for(int i = 1; i <= k; ++i) ans += dp[n][n][i][0] + dp[n][n][i][1]; writeln(ans); } }