我发现这个题可以spfa跑,然后就敲出来以下代码,给大家提供一种新思路
查看原帖
我发现这个题可以spfa跑,然后就敲出来以下代码,给大家提供一种新思路
709586
lllllluogu楼主2024/3/27 16:47
#include <bits/stdc++.h>
using namespace std;
int ans,a[300][300],f[300][300];
bool vis[300*300];
struct node{int x,y;};
queue<node>q;
int main(){
	int m,n;cin>>m>>n;
	for(int i=1;i<=m;i++)
	for(int j=1;j<=n;j++)cin>>a[i][j];
	q.push(node{m+1,n/2+1});
	memset(f,-0x3f,sizeof(f));
	f[m+1][n/2+1]=0;
	vis[(m+1)*n+n/2+1]=1;
	while(!q.empty()){
		node cur=q.front();q.pop();
		vis[cur.x*n+cur.y]=0;
		for(int i=-1;i<=1;i++){
			int tx=cur.x-1,ty=cur.y+i;
			if(tx<=0||tx>m||ty<=0||ty>n)continue;
			if(f[tx][ty]<f[cur.x][cur.y]+a[tx][ty]){
				f[tx][ty]=f[cur.x][cur.y]+a[tx][ty];
				if(!vis[tx*n+ty])q.push(node{tx,ty}),vis[tx*n+ty]=1;
			}
		}
	}
//	for(int i=1;i<=m;i++){
//		for(int j=1;j<=n;j++){
//			cout<<f[i][j]<<' ';
//		}cout<<'\n';
//	}
		for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)ans=max(ans,f[i][j]);
		cout<<ans;
		
}
2024/3/27 16:47
加载中...