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<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


int H,W,K;
int POW[13];
int dp[50][50][4][4096]; //dp[row][col][Kの残数][過去6回の移動ログ] = 最大値
char base_map[50][51];

bool rangeCheck(int row,int col){
	if(row >= 0 && row <= H-1 && col >= 0 && col <= W-1)return true;
	else{
		return false;
	}
}


int recursive(int row,int col,int back_count,int move_log,int moved_count){ //moved_log[]:インデックスが小さいほど新しい(右シフト)

	if(dp[row][col][back_count][move_log] != -1)return dp[row][col][back_count][move_log]; //計算済ならreturn

	if(row == H-1 && col == W-1 && back_count == K)return 0;

	int result_E = 0,result_S = 0,result_W = 0,result_N = 0;
	bool visited_E = false,visited_S = false,visited_W = false,visited_N = false;

	//過去の移動ログから、訪問済のマス情報を特定する
	int tmp_row = row,tmp_col = col;

	int log_array[6],tmp_log;

	tmp_log = move_log;
	for(int i = 0; i < 6; i++){
		log_array[i] = tmp_log%4;
		tmp_log /= 4;
	}

	for(int i = 0; i < min(6,moved_count); i++){
		switch(log_array[i]){ //ログを打ち消す方向に動く
		case 0: //East
			tmp_col--;
			break;
		case 1: //South
			tmp_row--;
			break;
		case 2: //West
			tmp_col++;
			break;
		case 3: //North
			tmp_row++;
			break;
		}

		if(tmp_row == row && tmp_col == col+1){ //右のマスと一致
			visited_E = true;
		}else if(tmp_row == row+1 && tmp_col == col){ //下のマスと一致
			visited_S = true;
		}else if(tmp_row == row && tmp_col == col-1){ //左のマスと一致
			visited_W = true;
		}else if(tmp_row == row-1 && tmp_col == col){ //上のマスと一致
			visited_N = true;
		}
	}

	int next_log = move_log%1024;
	int ret = -BIG_NUM;

	//右へ
	if(rangeCheck(row,col+1) == true && base_map[row][col+1] != '#'){
		if(visited_E == false){
			result_E += base_map[row][col+1]-'0';
		}
		int next_code = 4*next_log+0;
		result_E += recursive(row,col+1,back_count,next_code,moved_count+1);
		ret = max(ret,result_E);
	}

	//下へ
	if(rangeCheck(row+1,col) == true && base_map[row+1][col] != '#'){
		if(visited_S == false){
			result_S += base_map[row+1][col]-'0';
		}
		int next_code = 4*next_log+1;
		result_S += recursive(row+1,col,back_count,next_code,moved_count+1);
		ret = max(ret,result_S);
	}

	//左へ
	if(back_count < K && rangeCheck(row,col-1) == true && base_map[row][col-1] != '#'){
		if(visited_W == false){
			result_W += base_map[row][col-1]-'0';
		}
		int next_code = 4*next_log+2;
		result_W += recursive(row,col-1,back_count+1,next_code,moved_count+1);
		ret = max(ret,result_W);
	}

	//上へ
	if(back_count < K && rangeCheck(row-1,col) == true && base_map[row-1][col] != '#'){
		if(visited_N == false){
			result_N += base_map[row-1][col]-'0';
		}
		int next_code = 4*next_log+3;
		result_N += recursive(row-1,col,back_count+1,next_code,moved_count+1);
		ret = max(ret,result_N);
	}

	return dp[row][col][back_count][move_log] = ret;
}


int main(){

	for(int i = 0; i < 13; i++)POW[i] = pow(2,i);

	scanf("%d %d %d",&H,&W,&K);

	for(int row = 0; row < H; row++){
		scanf("%s",base_map[row]);
		for(int col = 0; col < W; col++){
			if(base_map[row][col] == '.'){
				base_map[row][col] = '0';
			}
		}
	}

	for(int row = 0; row < H; row++){
		for(int col = 0; col < W; col++){
			for(int i = 0; i <= 3; i++){
				for(int state = 0; state < POW[12]; state++)dp[row][col][i][state] = -1;
			}
		}
	}

	printf("%d\n",recursive(0,0,0,0,0));

	return 0;
}