60分求调
查看原帖
60分求调
1285086
zjx_coding楼主2024/5/10 21:01
#include<bits/stdc++.h>
using namespace std;
int n,m,dp[60][60],dp1[60][60],a[60][60],xx[5]= {0,1,0,-1,0},yy[5]= {0,0,1,0,-1};
bool b[60][60];
void dfs(int x,int y,bool g) {
	if (x==1&&y==1&&g==1) {
		return ;
	}
	if (x==n&&y==m&&g==0) {
		g=1;
		dp1[n][m]=dp[n][m];
	}
	int u,v;
	if (g==0) {
		for (int i=1; i<=2; i++) {
			u=x+xx[i];
			v=y+yy[i];
			if (u>=1&&u<=n&&v>=1&&v<=m) {
				if (b[u][v]==0) {
					if (dp[u][v]<dp[x][y]+a[u][v]) {
						dp[u][v]=dp[x][y]+a[u][v];
						b[u][v]=1;
						dfs(u,v,g);
						b[u][v]=0;
					}
				}
			}
		}
	} else if (g==1) {
		for (int i=3; i<=4; i++) {
			u=x+xx[i];
			v=y+yy[i];
			if (u>=1&&u<=n&&v>=1&&v<=m) {
				if (b[u][v]==0) {
					if (dp1[u][v]<dp1[x][y]+a[u][v]) {
						dp1[u][v]=dp1[x][y]+a[u][v];
						b[u][v]=1;
						dfs(u,v,g);
						b[u][v]=0;
					}
				}
			}
		}
	}
	return ;
}
int main() {
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=m; j++) {
			cin>>a[i][j];
		}
	}
	memset(b,0,sizeof(b));
	dfs(1,1,0);
	cout<<dp1[1][1];
	return 0;
}
2024/5/10 21:01
加载中...