[USACODec21Bronze] Question 3「Walking Home」题解

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);
    }
}
点赞

发表回复

电子邮件地址不会被公开。必填项已用 * 标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据