SEA404 限定步数巡查

难度梯度：T3+｜训练重点：DFS 回溯、距离与奇偶剪枝

题目描述

N×M 的地图中，从 S 出发恰好走 K 步到 E，每步上下左右移动到可走格，每个格子至多进入一次。问有多少条不同的路线。地图中 # 不可走，. 可走。不同路线指走过的格子序列不同。

出发格 S 在第 0 步已被访问；不能再次进入 S，也不能重复进入任何其他格子。到达 E 后路线立即结束。

输入格式

第一行 N M K，随后 N 行地图；恰有一个 S 和 E。

输出格式

输出路线数。

样例输入

2 2 2
S.
.E

样例输出

2

样例说明

可以先向右再向下，也可先向下再向右。

数据范围

1≤N,M≤7；1≤K≤min(15,NM-1)；答案保证在 64 位有符号整数内。

子任务

20 分：K≤7；30 分：无障碍；50 分：无附加限制。