35分dfs求优化
查看原帖
35分dfs求优化
78634
patricknao楼主2020/11/21 11:08
#include<bits/stdc++.h>
using namespace std;
int n,m;
int xx[4]={0,0,1,-1};
int yy[4]={0,1,0,0};
int a[1010][1010];
int b[1010][1010][3];//x坐标、y坐标、过来的方向
int maxn=-10000000;
void dfs(int x,int y,int dx,int dy,/*上个位置x、y坐标*/int t){      
	if(x==n&&y==m){
		maxn=max(maxn,t);
		return;
	}
	int dqwz=0;
	if(x!=1&&y!=1){		//记忆化 
		if(x-dx==1)dqwz=1;
		else if(x-dx==-1)dqwz=2;
		else if(y-dy==1)dqwz=3;
		if(t<b[x][y][dqwz])
			return;
		else
			b[x][y][dqwz]=t;		
	}
	for(int i=1;i<=3;i++){ 
		int tx=x+xx[i];
		int ty=y+yy[i];
		if(tx!=dx||ty!=dy){
			if(tx>=1&&tx<=n&&ty>=1&&ty<=m){
				dfs(tx,ty,x,y,t+a[tx][ty]);
			}
		}
	}
} 
int main(){
	memset(b,-10000000,sizeof(b));
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	b[1][1][1]=a[1][1];
	b[1][1][2]=a[1][1];
	b[1][1][3]=a[1][1];
	dfs(1,1,1,1,a[1][1]);
	cout<<maxn;
}

2020/11/21 11:08
加载中...