Problem: problem

JOI, who came to Australia for a trip, enjoyed sightseeing in various places and finally returned to Japan. Now, JOI is in the town with the international airport where the return flight departs. The town is divided into north, south, east and west, and each section has roads, souvenir shops, houses, and an international airport. JOI starts from the northwestern section and heads for the international airport in the southeastern section.

JOI can move from the current parcel to an adjacent parcel, but cannot enter a parcel with a house. Also, move only to the east or south section of the current section in order to make it in time for the flight. However, there is some time to spare, so you can move to the north or west section of the section you are up to K times.

When JOI enters the area where the souvenir shop is located, he buys souvenirs for his Japanese friends. JOI did a lot of research on the souvenir shops, so he knows which souvenir shop to buy and how many souvenirs to buy. Create a program to find the maximum number of souvenirs you can buy.

However, the time to buy souvenirs can be ignored, and if you visit the same souvenir shop more than once, you will only buy souvenirs the first time you visit.





Example

Input

5 4 2
...#
.#.#
.#73
8##.
....


Output

11

Solution (in CPP):

Solution:
#include <iostream>
#include <cstdio>
#include <vector>
#include <list>
#include <cmath>
#include <fstream>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <complex>
#include <iterator>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <stack>
#include <climits>
#include <deque>
#include <bitset>
#include <cassert>
#include <ctime>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
// adjust problem by problem
const double EPS=1e-8;
const double PI=acos(-1.0);
#ifdef __GNUC__
int popcount(int n){return __builtin_popcount(n);}
int popcount(ll n){return __builtin_popcountll(n);}
#endif
#ifndef __GNUC__
template<class T> int popcount(T n){int cnt=0;while(n){if(n%2)cnt++;n/=2;}return cnt;}
#endif
template<class T>int SIZE(T a){return a.size();}
template<class T>string IntToString(T num){string res;stringstream ss;ss<<num;return ss.str();}
template<class T>T StringToInt(string str){T res=0;for(int i=0;i<SIZE(str);i++)res=(res*10+str[i]-'0');return res;}
template<class T>T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template<class T>T lcm(T a,T b){return a/gcd(a,b)*b;}
template<class T> void PrintSeq(T &a,int sz){for(int i=0;i<sz;i++){cout<<a[i];if(sz==i+1)cout<<endl;else cout<<' ';}}
bool EQ(double a,double b){return abs(a-b)<EPS;}
void fastStream(){cin.tie(0);std::ios_base::sync_with_stdio(0);}
vector<string> split(string str,char del){
  vector<string> res;
  for(int i=0,s=0;i<SIZE(str);i++){
    if(str[i]==del){if(i-s!=0)res.push_back(str.substr(s,i-s));s=i+1;}
    else if(i==SIZE(str)-1){res.push_back(str.substr(s));}
  }
  return res;
}

int H,W,K;
char field[51][51];
int dp[51][51][1<<10][4][4];
bool used[51][51][1<<10][4][4];

const int dy[]={-1,0,1,0},dx[]={0,1,0,-1};
pii getNxtMaskAndVal(int cy,int cx,int mask,int my,int mx,int ang){
  int nmask=mask;
  int oy=cy+my;
  int ox=cx+mx;
  int cnt=0;
  int val=0;
  map<pii,int> m;
  for(int i=-3;i<=0;i++)
    for(int j=0;abs(i)+abs(j)<=3;j--)
      m[pii(i+oy,j+ox)]=cnt,cnt++;
  if(ang==0||ang==3){
    int ny=cy+dy[ang];
    int nx=cx+dx[ang];
    int nidx=m[pii(ny,nx)];
    if(ny>=0&&nx>=0&&ny<H&&nx<W&&field[ny][nx]!='#'){
      if(field[ny][nx]!='.'&&!((nmask>>nidx)&1))
        val+=field[ny][nx]-'0';
    }
    nmask|=(1<<nidx);
  }
  // 全体のビット右にをシフト
  else if(ang==1){
    int ny=cy+dy[ang];
    int nx=cx+dx[ang];
    nmask=0;
    nmask|=(((mask>>1)&1)<<2);
    nmask|=(((mask>>3)&1)<<4);
    nmask|=(((mask>>4)&1)<<5);
    nmask|=(((mask>>6)&1)<<7);
    nmask|=(((mask>>7)&1)<<8);
    nmask|=(((mask>>8)&1)<<9);
    int nidx=m[pii(cy,cx)];
    if(ny>=0&&nx>=0&&ny<H&&nx<W&&field[ny][nx]!='#'){
      if(field[ny][nx]!='.'&&!((nmask>>nidx)&1))
        val+=field[ny][nx]-'0';
    }
    nmask|=(1<<nidx);
  }
  // 下方向にビットをシフト
  else if(ang==2){
    int ny=cy+dy[ang];
    int nx=cx+dx[ang];
    nmask=0;
    nmask|=(((mask>>1)&1)<<0);
    nmask|=(((mask>>3)&1)<<1);
    nmask|=(((mask>>4)&1)<<2);
    nmask|=(((mask>>6)&1)<<3);
    nmask|=(((mask>>7)&1)<<4);
    nmask|=(((mask>>8)&1)<<5);
    int nidx=m[pii(cy,cx)];
    if(ny>=0&&nx>=0&&ny<H&&nx<W&&field[ny][nx]!='#')
      if(field[ny][nx]!='.'&&!((nmask>>nidx)&1))
        val+=field[ny][nx]-'0';
    nmask|=(1<<nidx);
  }
  return pii(nmask,val);
}

struct Sit{
  int cy,cx,mask,my,mx;
  Sit(){}
  Sit(int cy_,int cx_,int mask_,int my_,int mx_){
    cy=cy_;
    cx=cx_;
    mask=mask_;
    my=my_;
    mx=mx_;
  }
  bool operator<(const Sit&sit)const{
    return true;
  }
};
typedef pair<int,Sit> iSit;

const int INF=(1<<30);
int dfs(int cy,int cx,int mask,int my,int mx){
  if(used[cy][cx][mask][my][mx])return dp[cy][cx][mask][my][mx];
  int res=-INF;
  int leftK=K-(my+mx);
  for(int i=0;i<4;i++){
    int ny=cy+dy[i];
    int nx=cx+dx[i];
    if(ny>=0&&nx>=0&&ny<H&&nx<W&&field[ny][nx]!='#'){
      pii p=getNxtMaskAndVal(cy,cx,mask,my,mx,i);
      int nmask=p.first;
      int nAddVal=p.second;
      // cout<<nAddVal<<endl;
      if(leftK>0&&(i==0||i==3)){
        res=max(res,dfs(ny,nx,nmask,my+abs(dy[i]),mx+abs(dx[i]))+nAddVal);
      }
      else if((i==1||i==2)){
        res=max(res,dfs(ny,nx,nmask,my,mx)+nAddVal);
      }
    }
  }
  if(cy==H-1&&cx==W-1)res=max(res,0);
  used[cy][cx][mask][my][mx]=true;
  return dp[cy][cx][mask][my][mx]=res;
}

int dijkstra(){
  memset(dp,-1,sizeof(dp));
  dp[0][0][1<<6][0][0]=0;
  priority_queue<iSit> pq;
  pq.push(make_pair(0,Sit(0,0,1<<6,0,0)));
  while(pq.size()){
    iSit is=pq.top();pq.pop();
    int cval=is.first;
    Sit cSit=is.second;
    int cy=cSit.cy,cx=cSit.cx,mask=cSit.mask,my=cSit.my,mx=cSit.mx;
    if(dp[cy][cx][mask][my][mx]>cval)continue;
    int leftK=K-(my+mx);
    for(int i=0;i<4;i++){
      int ny=cy+dy[i];
      int nx=cx+dx[i];
      if(ny>=0&&nx>=0&&ny<H&&nx<W&&field[ny][nx]!='#'){
        pii p=getNxtMaskAndVal(cy,cx,mask,my,mx,i);
        int nmask=p.first;
        int nAddVal=p.second;
        if(leftK>0&&(i==0||i==3)&&dp[ny][nx][nmask][my+abs(dy[i])][mx+abs(dx[i])]<cval+nAddVal){
          dp[ny][nx][nmask][my+abs(dy[i])][mx+abs(dx[i])]=cval+nAddVal;
          pq.push(make_pair(cval+nAddVal,Sit(ny,nx,nmask,my+abs(dy[i]),mx+abs(dx[i]))));
        }
        else if((i==1||i==2)&&dp[ny][nx][nmask][my][mx]<cval+nAddVal){
          dp[ny][nx][nmask][my][mx]=cval+nAddVal;
          pq.push(make_pair(cval+nAddVal,Sit(ny,nx,nmask,my,mx)));
        }
      }
    }
  }
  int res=0;
  for(int mask=0;mask<(1<<10);mask++)
    for(int i=0;i<3;i++)
      for(int j=0;j<3;j++)
        res=max(res,dp[H-1][W-1][mask][i][j]);
  return res;
}

int main(){
  cin>>H>>W>>K;
  for(int i=0;i<H;i++)
    for(int j=0;j<W;j++)
      cin>>field[i][j];
  memset(dp,-1,sizeof(dp));
  // assert(dfs(0,0,(1<<6),0,0)==dijkstra());
  cout<<dfs(0,0,(1<<6),0,0)<<endl;
  //cout<<dijkstra()<<endl;
  
  return 0;
}