社区讨论
40分惨案??
P5003跳舞的线 - 乱拐弯参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @mi869irw
- 此快照首次捕获于
- 2025/11/21 09:19 4 个月前
- 此快照最后确认于
- 2025/11/21 09:19 4 个月前
CPP
#include<bits/stdc++.h>
#define ink 2147483647
using namespace std;
int n,m;
string s[1010];
int f[1010][1010][2];
int main(){
std::ios::sync_with_stdio(false);
cin>>n>>m;
for(register int i=1;i<=n;++i) cin>>s[i],s[i]=' '+s[i];
f[1][1][0]/*右*/=f[1][1][1]/*下*/=0;
for(register int i=1;i<=n;++i)
for(register int j=1;j<=m;++j){
if(i==1&&j==1) continue;
if(s[i][j]=='#'){
f[i][j][0]=f[i][j][1]=-1;
continue;
}
int maxn=-1;
j>1&&f[i][j-1][0]!=-1?maxn=max(maxn,f[i][j-1][0]):0;
i>1&&f[i-1][j][1]!=-1?maxn=max(maxn,f[i-1][j][1]+1):0;
f[i][j][0]=maxn;
maxn=-1;
j>1&&f[i][j-1][0]!=-1?maxn=max(maxn,f[i][j-1][0]+1):0;
i>1&&f[i-1][j][1]!=-1?maxn=max(maxn,f[i-1][j][1]):0;
f[i][j][1]=maxn;
}
int maxn=-1;
f[n][m][0]!=-1?maxn=max(f[n][m][0],maxn):0;
f[n][m][1]!=-1?maxn=max(f[n][m][0],maxn):0;
if(maxn==-1){
cout<<-1<<endl;
return 0;
}
else cout<<maxn<<" ";
f[1][1][0]/*右*/=f[1][1][1]/*下*/=0;
for(register int i=1;i<=n;++i)
for(register int j=1;j<=m;++j){
if(i==1&&j==1) continue;
if(s[i][j]=='#'){
f[i][j][0]=f[i][j][1]=-1;
continue;
}
int minn=ink;
j>1&&f[i][j-1][0]!=-1?minn=min(minn,f[i][j-1][0]):0;
i>1&&f[i-1][j][1]!=-1?minn=min(minn,f[i-1][j][1]+1):0;
minn==ink?f[i][j][0]=-1:f[i][j][0]=minn;
minn=ink;
j>1&&f[i][j-1][0]!=-1?minn=min(minn,f[i][j-1][0]+1):0;
i>1&&f[i-1][j][1]!=-1?minn=min(minn,f[i-1][j][1]):0;
minn==ink?f[i][j][1]=-1:f[i][j][1]=minn;
}
int minn=ink;
f[n][m][0]!=-1?minn=min(minn,f[n][m][0]):0;
f[n][m][1]!=-1?minn=min(minn,f[n][m][1]):0;
cout<<minn<<endl;
return 0;
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...