OI题库

就象所有奶牛偶尔发生的事情那样，贝茜在森林里迷路了！她急切的想回到住所，但不知道该怎么走。
这个森林可以被想象成一个R*C的网格(1 <= R <= 5; 1 <= C<= 5)。贝茜的位置是左下角，也就是(1,1)位置。住所在右上角，也就是(R,C)位置。在网格中的每一个格子要么是空的(用"."表示)，要么长着树(用"T"表示)。当然，贝茜和住所的格子没长树。
你需要帮忙确定贝茜从初始位置到住所步距离最多为K(1 <= K <= R * C)的不同路的条数。
例如，考虑下面的森林:
....
.T..
....

贝茜有若干条路到达右上角，下面是所有七条路径及其长度(访问的格子数)

	cdef bT.. a...	...f .T.e abcd	..ef .Td. abc.	..gh .Tfe abcd	cdeh bTfg a...	cdej bTfi a.gh	...f .Tde abc.
长度:	6	6	6	8	8	10	6

输入格式：
第一行：三个用空格隔开的整数：R,C和K
第2..R+1行：第i+1行包含C个字符表示森林的第R+1-i行(中间没有空格)

输入样例(file backbarn.in):
3 4 6
....
.T..
....
解释：这个森森是一个3*4的网络。一棵单独的树长在几乎是正中间。到终点不能超过六步。

输出格式：
第一行：一个整数，表示能回到住所的，不超过K的不同路径数。注意这个数是适合用一个无符号32位整数表示。

输出样例(file backbarn.out):
4
解释：有几条路能完成回到住所，只有四条是不超过六步的。