记录编号	41377	评测结果	AAAAAA
题目名称	948.返回住所	最终得分	100
用户昵称	H J H	是否通过	通过
代码语言	Pascal	运行时间	0.001 s
提交时间	2012-07-22 15:23:22	内存使用	0.17 MiB

var
r,c,i,j,k,n:longint;
a:array[0..100,0..100]of char;

procedure dfs(x,y,s:longint);
begin
if s>k then exit;
if (x=r)and(y=c)and(s<=k)  then begin inc(n); exit; end;

a[x,y]:='*';
if (a[x+1,y]='.')and(x+1<=r) then dfs(x+1,y,s+1);
if (a[x,y+1]='.')and(y+1<=c) then dfs(x,y+1,s+1);
if (a[x-1,y]='.')and(x-1>0)  then dfs(x-1,y,s+1);
if (a[x,y-1]='.')and(y-1>0)  then dfs(x,y-1,s+1);
a[x,y]:='.';
end;

begin
assign(input,'backbarn.in');
reset(input);
assign(output,'backbarn.out');
rewrite(output);

readln(r,c,k);
fillchar(a,sizeof(a),0);
for i:=r downto 1 do
    begin
    for j:=1 to c do read(a[i,j]);
    readln;
    end;
n:=0;
dfs(1,1,1);
write(n);

close(input);
close(output);
end.