记录编号	41357	评测结果	AAAAAA
题目名称	返回住所	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2012-07-22 12:38:41	内存使用	0.29 MiB

/*
* Problem  : backbarn
* Contest  : USACO Contest
* Author   : Yee-fan Zhu
* Date     : July 22,2012
*/ 
#include <cstdlib>
#include <cstdio>
using namespace std;
const int MAXN=7;
const int step[5][2]={{0,0},{1,0},{-1,0},{0,1},{0,-1}};
int mat[MAXN][MAXN];
int flag[MAXN][MAXN];
int N,M,K,ans=0;

inline void init()
{
	scanf("%d %d %d\n",&N,&M,&K);
	char c;
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=M;j++)
		{
			c=0;
			while(c!='.' && c!='T') 
				scanf("%c",&c);
			if(c=='.') mat[i][j]=1;
			else mat[i][j]=0;	
		}
	}
}

void dfs(int x,int y,int deep)
{
	int tx,ty;
	if(x==N && y==M)
	{
		if(deep<=K) ans++;
		flag[x][y]=0;
		return;
	}
	for(int i=1;i<=4;i++)
	{
		tx=x+step[i][0];
		ty=y+step[i][1];
		if(tx<1 || tx>N || ty<1 || ty>M) continue;
		if(!mat[tx][ty] || flag[tx][ty]) continue;
		flag[tx][ty]=1;
		dfs(tx,ty,deep+1);
		flag[tx][ty]=0;
	}
}

int main()
{
	freopen("backbarn.in","r",stdin);
	freopen("backbarn.out","w",stdout);
	init();	
	flag[1][1]=1;
	dfs(1,1,1);
	printf("%d\n",ans);
	return 0;
}