本文主要是介绍uva 10913 Walking on a Grid，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：有一个大小有N（最多75）的方格，要你从（1，1）走到（n,n）。有如下规则：你只有三个方向，左、右、下。不能走出方格。一个方格只能走一次。你要保证你的路径上的格子的和最大。你最多只能走k(最多为5)个负权值的格子，从起点到终点。
要注意，因为可以向右走，所以定义三维状态可能有问题，所以定义了四维，表示从当前点向左右下走能得到的最大的值。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
#define LL long long
#define INF -((LL)1<<60)
const int N=80;
LL data[N][N],map[N][N][7][3];
bool vis[N][N][7][3],grid[N][N];
int n,dir[3][2]={{0,1},{1,0},{0,-1}};
bool check(int,int);
LL dp(int,int,int,int);
int main()
{int k,t_cnt=0;while(scanf("%d%d",&n,&k)!=EOF){if(n==0&&k==0) break;memset(vis,0,sizeof(vis));memset(grid,0,sizeof(grid));for(int i=1;i<=n;i++){for(int j=1;j<=n;j++) scanf("%lld",&data[i][j]);}if(data[n][n]<0) k--;LL res=dp(1,1,k+1,1);printf("Case %d: ",++t_cnt);if(res!=INF) printf("%lld\n",res);else puts("impossible");}return 0;
}
LL dp(int x,int y,int z,int r)
{bool &flag=vis[x][y][z][r];LL &res=map[x][y][z][r];if(flag) return res;else if((x==n&&y==n)||z==0){flag=1;if(z==0) res=INF;else res=data[x][y];return res;}else{res=INF;for(int i=0;i<3;i++){int xx=x+dir[i][0],yy=y+dir[i][1],t=0;if(data[x][y]<0) t=-1;if(check(xx,yy)&&!grid[xx][yy]){if((r==0&&i==2)||(r==2&&i==0)) continue;grid[xx][yy]=1;LL temp=dp(xx,yy,z+t,i);if(temp!=INF) res=max(res,temp+data[x][y]);grid[xx][yy]=0;}}flag=1;return res;}
}
bool check(int x,int y)
{return x>=1&&x<=n&&y>=1&&y<=n;
}
这篇关于uva 10913 Walking on a Grid的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
