30pts求调
查看原帖
30pts求调
1162093
jimmy0926楼主2024/4/12 19:54
#include <bits/stdc++.h>
using namespace std;
int n,m,a[1001][1001];
const int dx[]={-1,0,+1},
		  dy[]={0,+1,0};
bool vis[1001][1001];
long long ans=-0x8000000000000000,f[1001][1001][3];
void dfs(int,int,long long);

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	memset(f,0xcf,sizeof f);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
			cin>>a[i][j];
	}
	dfs(1,1,a[1][1]);
	cout<<max({f[n][m][0],f[n][m][1],f[n][m][2]});
	return 0;
}
void dfs(int x,int y,long long sum)
{
	if(x==n && y==m)
		return;

	for(int i=0;i<3;i++)
	{
		int nx=x+dx[i],ny=y+dy[i];
		if(nx<1 || ny<1 || nx>n || ny>m || vis[nx][ny])
			continue;
		if(sum+a[nx][ny]<=f[nx][ny][i])
			continue;
		f[nx][ny][i]=sum+a[nx][ny];
		vis[nx][ny]=1;
		dfs(nx,ny,f[nx][ny][i]);
		vis[nx][ny]=0;
	}
}

thx,QWQthx , QWQ

2024/4/12 19:54
加载中...