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

#define MAX 6
#include <fstream>
using namespace std;

int sum=0,m,n,k,f[MAX][MAX]={0},road[MAX*MAX]={0},passed[MAX][MAX]={0};
int going(int x,int y,int step)
{
	if(!f[x][y]) return 0;//碰到树
	else
	{
		if(x==m&&y==n)//如果到达终点，更新符合条件路径数量
		{
			if(step<=k)sum++;
		}
		else//没有到达终点，继续以该点为中心试探四个方向
		{
			passed[x][y]=1;//要离开改点之前，标记改点已走过，避免转圈
			if(y+1<=n&&f[x][y+1]&&!passed[x][y+1])going(x,y+1,step+1);//E
			if(x+1<=m&&f[x+1][y]&&!passed[x+1][y])going(x+1,y,step+1);//s
			if(y-1>=1&&f[x][y-1]&&!passed[x][y-1])going(x,y-1,step+1);//W
			if(x-1>=1&&f[x-1][y]&&!passed[x-1][y])going(x-1,y,step+1);//N
			passed[x][y]=0;//回溯回来后将改点"已走过"的标记清除
		}
	}
	return 0;
}

int main ()
{
	int i,j;char ch;
	ifstream fin("backbarn.in");
	ofstream fout("backbarn.out");
	fin>>m>>n>>k;
	for(i=1;i<=m;i++)
		for(j=1;j<=n;j++)
		{
			fin>>ch;
			if(ch=='.')f[i][j]=1;
			if(ch=='T')f[i][j]=0;
		}
	going(1,1,1);//开始出发
	fout<<sum<<endl;
	fin.close();
	fout.close();
	return 0;
}