返回住所

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 backbarn.in 输出文件 backbarn.out


就象所有奶牛偶尔发生的事情那样,贝茜在森林里迷路了!她急切的想回到住所,但不知道该怎么走。
这个森林可以被想象成一个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
解释:有几条路能完成回到住所,只有四条是不超过六步的。