UVa:10913 Walking on a Grid

지난달에 게이지가 이 문제에 걸렸는데, 주로 왼쪽으로 갈 수 있는 곳에 얽혀 있었다.
오늘 회절동계로 마침내 방법을 생각해냈다.
저녁에 구체적인 사고방식을 쓰고 먼저 코드를 붙여라.
 

#include <cstdio>
#include <cstring>
#include <iostream>
#define INF -2139062144
using namespace std;
int main()
{
    int n,K,kase=0;
    while(scanf("%d%d",&n,&K)&&!(!n&&!K))
    {
        int grid[80][80]= {0};
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=n; ++j)
                scanf("%d",&grid[i][j]);
        int dp[80][80][10][5];
        memset(dp,0x80,sizeof(dp));
        dp[1][0][0][1]=0;
        for(int i=1; i<=n; ++i)
        {
            int v;
            for(int j=1; j<=n; ++j)
            {
                if(grid[i][j]>=0) v=0;
                else v=1;
                for(int k=0; k<=K; ++k)
                {
                    dp[i][j][k+v][1]=max(dp[i][j-1][k][1],dp[i-1][j][k][0]);
                    if(dp[i][j][k+v][1]!=INF) dp[i][j][k+v][1]+=grid[i][j];
                }
            }
            for(int j=n; j>=1; --j)
            {
                if(grid[i][j]>=0) v=0;
                else v=1;
                for(int k=0; k<=K; ++k)
                {
                    dp[i][j][k+v][2]=max(dp[i][j+1][k][2],dp[i-1][j][k][0]);
                    if(dp[i][j][k+v][2]!=INF) dp[i][j][k+v][2]+=grid[i][j];
                }
            }
            for(int j=1; j<=n; ++j)
                for(int k=0; k<=K; ++k)
                    dp[i][j][k][0]=max(dp[i][j][k][1],dp[i][j][k][2]);
        }
        int ans=INF;
        for(int i=0; i<=K; ++i)
            ans=max(dp[n][n][i][0],ans);
        printf("Case %d: ",++kase);
        if(ans==INF) puts("impossible");
        else printf("%d
",ans);
    }
    return 0;
}