14048 - 走迷宫 Ⅶ

在一个n行m列的二维网格中，机器人需要从左上角(1,1)移动到右下角(n,m)。

二维网格中有若干障碍物，它们不能经过也不能停留。

小项在设置机器人预设了t条指令，每个指令使得机器人为朝向（上/下/左/右）的其中一种。

也就是说，机器人的移动过程是：设定为第1条指令的方向->沿着方向移动若干步(也可以不移动)->设定为第2条指令的方向->沿着方向移动若干步(也可以不移动)......

求机器人有多少种不同的移动路径，使得从左上角(1,1)移动到右下角(n,m)。

两个方案不同，指的是存在同一个指令执行之后移动的步数不同

输入第一行为n、m、t。分别是网格的行数、列数、机器人指令的数量。

第二行t个数字。表示机器人指令的移动方向 0代表左 1代表右 2代表上 3代表下

接下来n行，每行m个字符 '.'表示可以移动的网格，'#'表示障碍物。

一个数字表示方案数

样例网格为5行5列，机器人依次按照右、下、右的方向移动。地图中无障碍。

移动方案5种如下图

1 \leq n,m,t \leq 15

入门教程