1055: 返回牛棚

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:52 通过:18

题目描述


和其他奶牛偶尔一样,贝茜在森林里摸迷了路。她急切地想回到牛棚,但是没有想好怎么走。

森林被分成了R x C (1 <= R <= 5; 1 <= C <= 5)个格子。贝茜目前所处的位置是左下角;牛棚位于右上角;每个单位的格子要么是空的(用"."表示)或是树(用"T"表示).贝茜的位置和牛棚的位置永远是空的。

给出正方形区域,贝茜可以走到区域的任意地方(只要该位置许可的话)。贝茜是一头相当聪明的奶牛,返回牛棚走的路径,相同的道路不会重复两次。

给出贝茜从现在的位置返回牛棚的路线长度K (1 <= K <= R * C),求出一共走K步可以达到牛棚的不同走法的总数。

 

例如,现有森林的数据如下:

        ....

        .T..

        ....

 

贝茜肯定能找出走到牛棚的方法,这是所有的7种走到牛棚的方法。(字母表示走的先后顺序):

 

         cdef  ...f  ..ef  ..gh  cdeh  cdej  ...f  

         bT..  .T.e  .Td.  .Tfe  bTfg  bTfi  .Tde  

         a...  abcd  abc.  abcd  a...  a.gh  abc.  

长度 :     6     6     6     8     8    10    6



输入格式


* 第 1 行: 三个用空格隔开的整数: R, C, K

* 第 2 至 R+1 行: 森林的数据 (无空格)



输出格式



* 一共走K步可以达到牛棚的不同走法的总数



输入样例 复制

3 4 6
....
.T..
....

输出样例 复制

4