好久没写过这么码农的题目了
dp[a][b][c][d][bound] 表示猫在(a, b) 老鼠在(c, d) 当前一共bound步的状态下谁赢
INF 老鼠输
-INF老鼠赢

对于每一步来说 老鼠和猫都希望自己赢 所以老鼠取min 猫取max
最后判断猫和老鼠谁赢了

const int M = 10, N = 129;
const int INF = 100000;

int dp[M][M][M][M][N];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

class Solution {
public:
    vector<string> grid;
    int catJump, mouseJump;
    int ex, ey;

    // 老鼠先移动     INF:老鼠输
    int dfs(int cx, int cy, int mx, int my, int bound){
        if(bound >= 128) return dp[cx][cy][mx][my][bound] = INF;
        if(cx == ex && cy == ey) return dp[cx][cy][mx][my][bound] = INF;
        if(mx == ex && my == ey) return dp[cx][cy][mx][my][bound] = -INF;
        if(mx == cx && my == cy) return dp[cx][cy][mx][my][bound] = INF;
        if(dp[cx][cy][mx][my][bound] != -1) return dp[cx][cy][mx][my][bound];

        int e = ((bound % 2 == 0) ? mouseJump : catJump);
        int x = ((bound % 2 == 0) ? mx : cx);
        int y = ((bound % 2 == 0) ? my : cy);
        int t = ((bound % 2 == 0) ? INF : -INF);
        for(int j = 0;j < 4;j ++ ){
            for(int i = 0;i <= e;i ++ ){
                int nx = x + i * dx[j], ny = y + i * dy[j];
                if(nx < 0 || nx >= grid.size() || ny < 0 || ny >= grid[0].size()){
                    continue;
                }
                if(grid[nx][ny] == '#'){
                    break;
                }
                if(bound % 2 == 0) t = min(dfs(cx, cy, nx, ny, bound + 1), t);
                else t = max(dfs(nx, ny, mx, my, bound + 1), t);
            }
        }
        return dp[cx][cy][mx][my][bound] = t;
    }
    bool canMouseWin(vector<string>& _grid, int catJump, int mouseJump) {
        memset(dp, -1, sizeof dp);
        grid = _grid; this->catJump = catJump, this->mouseJump = mouseJump;
        int cx, cy, mx, my;
        for(int i = 0;i < grid.size();i ++ ){
            for(int j = 0;j < grid[0].size();j ++ ){
                if(grid[i][j] == 'C') cx = i, cy = j;
                if(grid[i][j] == 'M') mx = i, my = j;
                if(grid[i][j] == 'F') ex = i, ey = j;
            }
        }
        int t = dfs(cx, cy, mx, my, 0);
        if(t >= INF) return false;
        return true;
    }
};