记搜90分 玄关求调
查看原帖
记搜90分 玄关求调
1048854
dlover楼主2024/10/17 10:02
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int N=1050;
ll n , m , f[4][N][N] , d[N][N]={0};
ll mx(ll a,ll b,ll c)
{
	return max(a,max(b,c));
}
bool vis[N][N]={0};
bool ok(int x,int y)
{
	return !( x<1 || x>n || y<1 || y>m );
}
int dfs(int from,int x,int y)
{
	if(f[from][x][y]!=-1e8) return f[from][x][y]; 
	else
	{
		if(x==1&&y==1)
		{
			f[from][1][1]=d[1][1];
			return f[from][1][1];
		}
		else
		{
			ll ans1=-1e8,ans2=-1e8,ans3=-1e8;
			vis[x][y]=1;
			if(from==1)
			{
				if(ok(x,y-1)&&!vis[x][y-1])
				{
					ans1=mx(dfs(1,x,y-1),dfs(2,x,y-1),dfs(3,x,y-1));
				}
			}
			if(from==2)
			{
				if(ok(x-1,y)&&!vis[x-1][y])
				{
					ans2=max(dfs(1,x-1,y),dfs(2,x-1,y));
				}
			}
			if(from==3)
			{
				if(ok(x+1,y)&&!vis[x+1][y])
				{
					ans3=max(dfs(1,x+1,y),dfs(3,x+1,y));
				}
			}
			vis[x][y]=0;
			f[from][x][y]=mx(ans1,ans2,ans3)+d[x][y];
			return f[from][x][y];
		}
		
		
	}
}
int main()
{
	freopen("csp2020pj_number.in","r",stdin);
	freopen("csp2020pj_number.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>d[i][j];
			for(int t=1;t<=3;t++)
			{
				f[t][i][j]=-1e8;
			}
		}
	}
	cout<<max(dfs(1,n,m),dfs(2,n,m));
}

2024/10/17 10:02
加载中...