UVa 10913 - Walking on a Grid Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
using namespace std;   
long long n,K;
vector<vector<long long> > a;
vector<vector<vector<vector<long long> > > > dp;
//dir 1 is top,0 is left,2 is right
long long dfs(long long i,long long j,long long k,long long dir){
    if(i<0||i==n||j<0||j==n)
        return -1e9;
    k=(a[i][j]<0)?k-1:k;
    if(k<0)
        return -1e9;
    if(dp[i][j][k][dir]!=-1e8)
        return dp[i][j][k][dir];
    if(i==n-1&&j==n-1)
        return dp[i][j][k][dir]=a[i][j];
    long long ans=-1e9;
    ans=max(ans,dfs(i+1,j,k,1));
    if(dir!=2)ans=max(ans,dfs(i,j+1,k,0));
    if(dir!=0)ans=max(ans,dfs(i,j-1,k,2));
    if(ans!=-1e9)
        return dp[i][j][k][dir]=a[i][j]+ans;
    else
        return dp[i][j][k][dir]=-1e9;
}
int main(){
    long long c=1;
    while(1){
        cin>>n>>K;
        if(n==0&&K==0)
            return 0;
        a.assign(n,vector<long long>(n,0));
        dp.assign(n,vector<vector<vector<long long> > >(n,vector<vector<long long> >(K+1,(vector<long long>(3,-1e8)))));
        for(long long i=0;i<n;i++)
            for(long long j=0;j<n;j++)
                cin>>a[i][j];
        dp[0][0][K][0]=dfs(0,0,K,0);
        cout<<"Case "<<c++<<": ";
        if(dp[0][0][K][0]!=-1e9)
            cout<<dp[0][0][K][0]<<endl;
        else
            cout<<"impossible"<<endl;
    }
}