蒟蒻求调dp
查看原帖
蒟蒻求调dp
1220111
xiaoyang222楼主2024/1/23 10:37
#include <iostream>
#include <vector>
using namespace std;
int main(){
	int n,m;
	cin >> n >> m;
	vector<vector<bool>> a(n+1,vector<bool>(m+1,true));
	char c;
	for (int i=1;i<=n;++i){
		getchar();
		for (int j=1;j<=m;++j){
			c=getchar();
			if (c=='#'){
				a[i][j]=false;
			}
		}
	}
	vector<vector<vector<int>>> dp(n+1,
	vector<vector<int>>(m+1,vector<int>(2,n*m+5))),
	dp2(n+1,vector<vector<int>>(m+1,vector<int>(2,-1)));//0为向下,1为向右 
	dp[1][1][0]=dp[1][1][1]=0;
	for (int i=1;i<=n;++i){
		for (int j=1;j<=m;++j){
			if (i==j && i==1 || !a[i][j]){
				continue;
			}
			if (a[i][j-1]){
				dp[i][j][0]=min(dp[i][j-1][0],dp[i][j][0]);//没转弯 
				dp[i][j][0]=min(dp[i][j-1][1]+1,dp[i][j][0]);//转弯 
				dp2[i][j][0]=max(dp2[i][j-1][0],dp2[i][j][0]);//没转弯 
				dp2[i][j][0]=max(dp2[i][j-1][1]+1,dp2[i][j][0]);//转弯 
			}
			if (a[i-1][j]){
				dp[i][j][1]=min(dp[i-1][j][1],dp[i][j][1]);//没转弯 
				dp[i][j][1]=min(dp[i-1][j][0]+1,dp[i][j][1]);//转弯 
				dp2[i][j][1]=max(dp2[i-1][j][1],dp2[i][j][1]);//没转弯 
				dp2[i][j][1]=max(dp2[i-1][j][0]+1,dp2[i][j][1]);//转弯 
			}
		}
	}
	int ans1=max(dp2[n][m][0],dp2[n][m][1]),ans2=min(dp[n][m][0],dp[n][m][1]);
	if (ans2>n*m){
		cout<<-1<<endl;
	}else{
		cout<<ans1<<" "<<ans2<<endl;
	}
	return 0;
}

10pts

2024/1/23 10:37
加载中...