dp求调WA#3#8#10
查看原帖
dp求调WA#3#8#10
1258467
hao12345ia楼主2025/6/29 14:20

代码如下:

#include<bits/stdc++.h>
using namespace std;
int m,n;
char a[1001][1001];
int fxmin[1001][1001][2];
int fxmax[1001][1001][2];
int main(){
	cin>>m>>n;
	for(int i=1;i<=m;i++) {
		for(int j=1;j<=n;j++) {
			cin>>a[i][j]; 
		} 
	}
	if(a[1][1]=='#'){
		cout<<-1;
		return 0; 
	}
	if(n>=2&&a[1][2]!='#'){
		fxmin[1][2][1]=0;
	    fxmax[1][2][1]=0; 
	}
	if(m>=2 && a[2][1]!='#') {
		fxmin[2][1][0]=0;
	    fxmax[2][1][0]=0; 
	}
	memset(fxmin,0x3f,sizeof(fxmin));
	fxmin[1][1][1]=fxmin[1][1][0]=0;
	for(int i=1;i<=m; i++) {
		for(int j=1;j<=n;j++) {
			if(a[i][j]=='#'||(i==1&&j==1)){
				continue; 
			}
			if(j>1 && a[i][j-1]!='#'){
				fxmin[i][j][1]=min(fxmin[i][j][1],fxmin[i][j-1][0]+1);
				fxmin[i][j][1]=min(fxmin[i][j][1],fxmin[i][j-1][1]);
				fxmax[i][j][1]=max(fxmax[i][j][1],fxmax[i][j-1][0]+1);
				fxmax[i][j][1]=max(fxmax[i][j][1],fxmax[i][j-1][1]);
			}
			if(i>1 && a[i-1][j]!='#'){
				fxmin[i][j][0]=min(fxmin[i][j][0],fxmin[i-1][j][1]+1);
				fxmin[i][j][0]=min(fxmin[i][j][0],fxmin[i-1][j][0]);
				fxmax[i][j][0]=max(fxmax[i][j][0],fxmax[i-1][j][1]+1);
				fxmax[i][j][0]=max(fxmax[i][j][0],fxmax[i-1][j][0]); 
			} 
		} 
	}
	int min_turn=min(fxmin[m-1][n][1],fxmin[m][n-1][0]);
	int max_turn=max(fxmax[m][n-1][0],fxmax[m-1][n][1]);
	if(min_turn>=0x3f3f3f3f){
		cout<<-1; 
	}
	else{
		cout<<max_turn<<" "<<min_turn;
    }
}
/*
5 5
oooo#
ooooo
#oo#o
o#o#o
oo#oo
*/
2025/6/29 14:20
加载中...