社区讨论
请问这个思路为什么不对?
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 条回复,欢迎继续交流。
正在加载回复...