Programming Contest, 2005
I
Walking on a Grid
Input: standard inputOutput: standard output
Problemsetter:Sohel Hafiz
You will be given a square grid of sizeN × N.The top-left square has a coordinate of (1, 1) and that of bottom-right is (N, N). Your job is to walk from(1, 1)to(N, N).Very easy, right?That’s why you have to follow some rules when walking.
Input
Each case will start with two integersNandk.N ≤ 75andk ≤ 5.Each of the nextNlines will containNintegers each given in row major order. That is, the first integer of the first row is (1, 1) and the last integer of last row is (N, N). Input terminates with two zeros on a line.
Output
For every case output the case number. If it’s not possible to reach the destination meeting the above rules then output “impossible”, else print the maximum sum of integers of the path.
Sample Input
Output for Sample Input
4 11 2 3 -5-10 6 0 -1-10 -10 -10 20 0 0 14 01 2 3 -5-10 6 0 -1-10 -10 -10 20 0 0 10 0
Case1: 11Case 2: impossible
#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<string>#include<iostream>#include<queue>#include<cmath>#include<map>#include<stack>#include<bitset>using namespace std;#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )#define CLEAR( a , x ) memset ( a , x , sizeof a )typedef long long LL;typedef pair<int,int>pil;const int INF = 0x3f3f3f3f;const int maxn=80;LL mp[maxn][maxn];LL dp[maxn][maxn][10][4];//从(i,j)出发的最大int dr[][2]={1,0,0,1,0,-1};//threeint vis[maxn][maxn][10][4];int n,m;bool ok(int x,int y){if(x>=1&&x<=n&&y>=1&&y<=n) return true;return false;}LL dfs(int x,int y,int s,int d){if(s>m) return -INF;if(x==n&&y==n)return mp[n][n];if(vis[x][y][s][d])return dp[x][y][s][d];LL res=-INF;vis[x][y][s][d]=1;for(int i=0;i<3;i++){int xx=x+dr[i][0];int yy=y+dr[i][1];if((d==1&&i==2)||(d==2&&i==1)) continue;//从左来不能到右边去；右边同理if(ok(xx,yy)){int f=(mp[xx][yy]<0);LL temp=dfs(xx,yy,s+f,i);if(temp!=-INF) res=max(res,mp[x][y]+temp);}}dp[x][y][s][d]=res;return res;}int main(){int cas=1;while(~scanf("%d%d",&n,&m)&&(n+m)){CLEAR(vis,0);REPF(i,1,n)REPF(j,1,n) scanf("%lld",&mp[i][j]);CLEAR(dp,-INF);int x=(mp[1][1]<0);LL ans=dfs(1,1,x,0);printf("Case %d: ",cas++);if(ans==-INF) puts("impossible");else printf("%lld\n",ans);}return 0;}/*4 11 2 3 -5-10 6 0 -1-10 -10 -10 20 0 0 1*/
，这一秒不放弃，下一秒就会有希望。
