社区讨论

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 条回复,欢迎继续交流。

正在加载回复...