社区讨论

请问这个思路为什么不对?

P5003跳舞的线 - 乱拐弯参与者 1已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@m44zbc1p
此快照首次捕获于
2024/12/01 10:25
去年
此快照最后确认于
2025/11/04 13:32
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1010;
char mp[maxn][maxn];
int f[2][maxn][maxn];//max
int g[2][maxn][maxn];//min

void print(int a[2][maxn][maxn], int state, int n, int m){
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= m; j++){
            printf("%-11d ", a[state][i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

int main(){
    int n, m;
    scanf("%d%d",&n, &m);
    getchar();
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            mp[i][j] = getchar();
            if(mp[i][j] == '#'){
                f[0][i][j] = f[1][i][j] = -0x3f3f3f3f;
                g[0][i][j] = g[1][i][j] = 0x3f3f3f3f;
            }
        }
        getchar();
    }
    for(int i = 2; i <= n; i++){
        g[0][i][0] = g[1][i][0] = 0x3f3f3f3f;
        f[0][i][0] = f[1][i][0] = -0x3f3f3f3f;
    }
    for(int j = 2; j <= m; j++){
        g[1][0][j] = g[0][0][j] = 0x3f3f3f3f;
        f[1][0][j] = f[0][0][j] = -0x3f3f3f3f;
    }
    for(int i = 1; i <= n; i++){
       for(int j = 1; j <= m; j++){
          if(i == 1 && j == 1) continue;
          if(mp[i][j] == '#') continue;
          f[0][i][j] = max(f[0][i][j-1], f[1][i][j-1]+1);
          f[1][i][j] = max(f[1][i-1][j], f[0][i-1][j]+1);
          g[0][i][j] = min(g[0][i][j-1], g[1][i][j-1]+1);
          g[1][i][j] = min(g[1][i-1][j], g[0][i-1][j]+1);
       } 
    }

    if(f[0][n][m] <= 0 && f[1][n][m] <= 0) printf("-1\n");
    else printf("%d %d\n", max(f[0][n][m], f[1][n][m])-1, min(g[0][n][m], g[1][n][m]));
    return 0;
}
/*
思路:
定义f[0][i][j]为到达i,j时方向朝右的最大拐弯次数,f[1][i][j]为到达i,j时方向朝下的最大拐弯次数。
g[0/1][i][j]为最小拐弯次数

f[0][i][j] 可以是j-1列方向朝下,向右拐到达的, 为f[1][i][j-1]+1
        也可以是j-1列方向朝右,直走到达的,为f[0][i][j-1]
所以
f[0][i][j] = max(f[1][i][j-1]+1, f[0][i][j-1]);

同理
f[1][i][j] = max(f[1][i-1][j], f[0][i-1][j]+1);
g[0][i][j] = min(g[0][i][j-1], g[1][i][j-1]+1);
g[1][i][j] = min(g[1][i-1][j], g[0][i-1][j]+1);

初始化:
给不可到达的状态设为最值
1.有#的点
2.0列0行
*/

回复

1 条回复,欢迎继续交流。

正在加载回复...