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 <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <queue>
#include <bitset>
#include <string>
using namespace std;

#define REP(i,n) for(int i=0; i<n; i++)
#define RPA(i,s,e) for(int i=s; i<=e; i++)
#define RPD(i,s,e) for(int i=s; i>=e; i--)
#define PB(a) push_back(a)
#define MP(i,s) make_pair(i,s)
#define SZ(a) (int)(a).size()
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cout << (a) << endl
#define PRT2(a,b) cout << (a) << " " << (b) << endl
#define PRT3(a,b,c) cout << (a) << " " << (b) << " " << (c) << endl

typedef vector<int> VI;
typedef long long LL;
typedef pair<int,int> P;

int h,w,k;
string ln;
int field[51][51];
int dp[51][51][4][4096];
int trans[4096][4][4];
int visit[4096][4][4];
vector<P> pos[4];

int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, -1, 1, 0};

void solve() {
	memset(dp, -1, sizeof(dp));
	dp[0][0][0][0] = 0;
	for(int used=0; used<=k; used++) {
		for(int y=0; y<h; y++) {
			for(int x=0; x<w; x++) {
				for(int mask=0; mask<(1<<11); mask++) {
					if(dp[x][y][used][mask] < 0) continue;

					for(int i=0; i<4; i++) {
						int nk = (i < 2) ? used + 1 : used;
						if(nk > 3) continue;

						int next = dp[x][y][used][mask];
						int nmask = trans[mask][used][i];
						int nx = x + dx[i];
						int ny = y + dy[i];
						if(nx >= 0 && ny >= 0 && nx < w && ny < h && field[nx][ny] >= 0) {
							if(!visit[mask][used][i]) next += field[nx][ny];
							dp[nx][ny][nk][nmask] = max(dp[nx][ny][nk][nmask], next);
						}
					}
				}
			}
		}
	}

	int ans = -1;
	for(int used=0; used<=k; used++) {
		for(int mask=0; mask<(1<<11); mask++) {
			ans = max(ans, dp[w-1][h-1][used][mask]);
		}
	}
	printf("%d\n", ans);
}

void prepare() {
	memset(trans, 0, sizeof(trans));
	memset(visit, 0, sizeof(visit));

	for(int used=0; used<=3; used++) {
		for(int y=-3; y<=3; y++) {
			for(int x=-3; x<=3; x++) {
				if(x == 0 && y == 0) continue;
				int drop = max(0, x) + max(0, y);
				int back = max(-x, 0) + max(-y, 0);
				if(drop <= used && back <= (3 - used)) pos[used].push_back(P(x, y));
			}
		}
	}

	for(int mask=0; mask<(1<<11); mask++) {
		for(int used=0; used<=3; used++) {
			for(int i=0; i<4; i++) {
				int nk = (i < 2) ? used + 1 : used;
				if(nk > 3) continue;

				int& bit = trans[mask][used][i];
				for(int y=-3; y<=3; y++) {
					for(int x=-3; x<=3; x++) {
						int n1 = -1;
						int n2 = -1;
						int nx = x - dx[i];
						int ny = y - dy[i];
						for(int j=0; j<pos[used].size(); j++) { // 前のマップでの場所の番号
							if(pos[used][j] == P(x, y)) n1 = j;
						}
						for(int j=0; j<pos[nk].size(); j++) { // 次のマップでの場所の番号
							if(pos[nk][j] == P(nx, ny)) n2 = j;
						}

						if(n1 >= 0 && n2 >= 0) {
							if(mask & (1 << n1)) bit |= (1 << n2); 
						}
					}
				}

				int t = -1;
				for(int j=0; j<pos[nk].size(); j++) {
					if(pos[nk][j] == P(-dx[i], -dy[i])) t = j;
				}
				if(t >= 0) {
					bit |= (1 << t);
				}

				for(int j=0; j<pos[used].size(); j++) {
					if((mask & (1<<j)) && pos[used][j] == P(dx[i], dy[i])) {
						visit[mask][used][i] = 1;
					}
				}
			}
		}
	}
}

void coding() {
	prepare();
	while(scanf("%d%d%d", &h, &w, &k)!=EOF) {
		for(int y=0; y<h; y++) {
			cin>>ln;
			for(int x=0; x<w; x++) {
				if(ln[x] == '#') field[x][y] = -1;
				if(ln[x] == '.') field[x][y] = 0;
				else field[x][y] = ln[x] - '0';
			}
		}
		solve();
	}
}

// #define _LOCAL_TEST

int main() {
#ifdef _LOCAL_TEST
	clock_t startTime = clock();
	freopen("a.in", "r", stdin);
#endif

	coding();

#ifdef _LOCAL_TEST
	clock_t elapsedTime = clock() - startTime;
	cout << endl;
	cout << (elapsedTime / 1000.0) << " sec elapsed." << endl;
	cout << "This is local test" << endl;
	cout << "Do not forget to comment out _LOCAL_TEST" << endl << endl;
#endif
}