LCP 31-变换的迷宫

某解密游戏中，有一个 N\*M 的迷宫，迷宫地形会随时间变化而改变，迷宫出口一直位于 (n-1,m-1) 位置。迷宫变化规律记录于 maze
中，maze[i] 表示 i 时刻迷宫的地形状态，"." 表示可通行空地，"#" 表示陷阱。 地形图初始状态记作
maze[0]，此时小力位于起点 (0,0)。此后每一时刻可选择往上、下、左、右其一方向走一步，或者停留在原地。
小力背包有以下两个魔法卷轴（卷轴使用一次后消失）： + 临时消除术：将指定位置在下一个时刻变为空地； + 永久消除术：将指定位置永久变为空地。
请判断在迷宫变化结束前（含最后时刻），小力能否在不经过任意陷阱的情况下到达迷宫出口呢？ 注意： 输入数据保证起点和终点在所有时刻均为空地。 示例
1： >输入：maze = [[".#.","#.."],["...",".#."],[".##",".#."],["..#",".#."]] >

输出：true > >解释： ![maze.gif](https://pic.leetcode-cn.com/1615892239-SCIjyf-
maze.gif) 示例 2： >输入：maze = [[".#.","..."],["...","..."]] > >输出：false >
解释：由于时间不够，小力无法到达终点逃出迷宫。 示例 3： >输入：maze = [["...","...","..."],[".##","###","##."],[".##","###","##."],[".##","###","##."],[".##","###","##."],[".##","###","##."],[".##","###","##."]]

输出：false > >解释：由于道路不通，小力无法到达终点逃出迷宫。 提示： - 1 <= maze.length <= 100
- 1 <= maze[i].length, maze[i][j].length <= 50 - maze[i][j] 仅包含
"."、"#"

解题思路

双百 %%%

f[时间，位置x，位置y，临时卷轴，永久卷轴]
Dfs(时间，位置x，位置y，临时卷轴，永久卷轴，永久卷轴使用位置x，永久卷轴使用位置y)

代码

public class Solution {
    int[] dx = {1, -1, 0, 0, 0}, dy = {0, 0, 1, -1, 0};
    int[,,,,] f = new int[101, 51, 51, 2, 2];
    public bool EscapeMaze(string[][] s) {
        int l = s.Length - 1, n = s[0].Length, m = s[0][0].Length;

        void Dfs(int t, int x, int y, int p, int q, int o, int k){
            if(t == l) f[t, x, y, p, q] = 1;
            if(x < 0 || y < 0 || x >= n || y >= m) return; 
            if(f[t, x, y, p, q] == 1 || t >= l) return;
            f[t, x, y, p, q] = 1;
            for(int i = 0; i < 5; i++){
                int u = x + dx[i], v = y + dy[i];
                if(u < 0 || v < 0 || u >= n || v >= m) continue;
                if(s[t + 1][u][v] == '#'){
                    if(o == u && k == v) Dfs(t + 1, u, v, p, q, o, k);
                    if(p == 1) Dfs(t + 1, u, v, p - 1, q, o, k);
                    if(q == 1) Dfs(t + 1, u, v, p, q - 1, u, v);
                }
                else Dfs(t + 1, u, v, p, q, o, k);
            }
        }

        Dfs(0, 0, 0, 1, 1, 0, 0);
        for(int t = 0; t < s.Length; t++){
            for(int p = 0; p < 2; p++){
                for(int q = 0; q < 2; q++){
                    if(f[t, n - 1, m - 1, p, q] == 1)
                        return true;
                }
            }
        }
        return false;
    }
}