913. 猫和老鼠

这一题的关键是抽象出来一个DP描述的博弈论问题，然后基于获胜条件给出策略优先级：
image.png
建模的难点在于，如何去评判平局的情况？
image.png
使用了一个笨但直观的上界取值，如果要证明更小的k值，emmmm，太复杂了，不会。
接下来就是，如何去体现决策的，“最优性”？或者说，如何体现假设博弈双方为理性角色
image.png
这里就是通过基于获胜目的的，决策的优先级来进行了定义，具体到代码中，就是使用，记忆化搜索，查询可选目的中的最优决策点，来进行移动，因此是类似一个DFS的思路：

  1. impl Solution {
  2.     /// 913. 猫和老鼠
  3.     pub fn cat_mouse_game(graph: Vec<Vec<i32>>) -> i32 {
  4.         /// 完成dfs搜索，注意，这里体现了博弈的过程，使用记忆化搜索完成决策优先级的描述
  5.         /// 0:平局draw，1:老鼠获胜，2:猫获胜
  6.         fn dfs(dp: &mut Vec<Vec<Vec<i32>>>, g: &Vec<Vec<i32>>, up: usize,
  7.                k: usize, i: usize, j: usize) -> i32 {
  8.             let mut ans = dp[k][i][j];
  9.             println!("[第{}步,鼠{}, 猫{}]", k, i, j);
  10.             println!("----->ans: {}", ans);
  11.             // 三种情况，如果搜索到的某个点，满足获胜条件、越过上界、没有走到这个情况
  12.             // 也即dfs的终止条件与继续条件
  13.             if i == 0 { ans = 1; }
  14.             else if i == j { ans = 2; }
  15.             else if k >= up { ans = 0; }
  16.             else if ans == -1 {
  17.                 // 新的情况，开始博弈
  18.                 // 对于老鼠来说：
  19.                 if (k & 1) == 0 {
  20.                     let (mut win, mut draw) = (false, false);
  21.                     for s in 0..g[i].len() {
  22.                         let step = g[i][s];
  23.                         let t = dfs(dp, g, up, k+1, step as usize, j); // 走向下一层的情况
  24.                         // 这里体现了优先级决策，我们在这里使用两个bool来进行记忆
  25.                         if t == 1 { win = true; }
  26.                         else if t == 0 { draw = true; }
  27.                         // 找到第一个最优的就剪枝出去了
  28.                         if win { break; }
  29.                     }
  30.                     // 借助if的执行顺序，其实是优先win的时候，然后平局，最后才是失败的时候
  31.                     println!("[mouse--]win:{}, draw:{}", win, draw);
  32.                     if win { ans = 1; }
  33.                     else if draw { ans = 0; }
  34.                     else { ans = 2; }
  35.                 }else {
  36.                     // 对于猫猫来说
  37.                     let (mut win, mut draw) = (false, false);
  38.                     for s in 0..g[j].len() {
  39.                         let step = g[j][s];
  40.                         // 不能走老鼠走过的地方
  41.                         if step == 0 { continue; }
  42.                         let t = dfs(dp, g, up, k+1, i, step as usize); // 走向下一层的情况
  43.                         // 这里体现了优先级决策，我们在这里使用两个bool来进行记忆
  44.                         if t == 2 { win = true; }
  45.                         else if t == 0 { draw = true; }
  46.                         // 找到第一个最优的就剪枝出去了
  47.                         if win { break; }
  48.                     }
  49.                     println!("[cat--]win:{}, draw:{}", win, draw);
  50.                     // 借助if的执行顺序，其实是优先win的时候，然后平局，最后才是失败的时候
  51.                     if win { ans = 2; }
  52.                     else if draw { ans = 0; }
  53.                     else { ans = 1; }
  54.                 }
  55.             }
  56.             dp[k][i][j] = ans;
  57.             println!("[===]Get ans: {}", ans);
  58.             ans
  59.         }
  61.         let len = graph.len();
  62.         // dp[k][i][j]，k步，上界2*n*n，i和j表示老鼠和猫的位置，n的范围
  63.         let mut dp = vec![vec![vec![-1; 55]; 55]; 2*55*55];
  64.         dfs(&mut dp, &graph, 2*len*len, 0, 1, 2)
  65.     }
  66. }

1728. 猫和老鼠 II

和上面一题比较，换汤不换药

import java.time.Clock;
class Solution {
    static int S = 8 * 8 * 8 * 8, K = 1000;
    static int[][] f = new int[S][K]; // mouse : 0 / cat : 1
    String[] g;
    int n, m, a, b, tx, ty;
    int[][] dirs = new int[][]{{1,0}, {-1,0}, {0,1}, {0,-1}};
    // mouse : (x, y) / cat : (p, q)
    int dfs(int x, int y, int p, int q, int k) {
        int state = (x << 9) | (y << 6) | (p << 3) | q;
        if (k == K - 1) return f[state][k] = 1;
        if (x == p && y == q) return f[state][k] = 1;
        if (x == tx && y == ty) return f[state][k] = 0;
        if (p == tx && q == ty) return f[state][k] = 1;
        if (f[state][k] != -1) return f[state][k];
        if (k % 2 == 0) { // mouse
            for (int[] di : dirs) {
                for (int i = 0; i <= b; i++) {
                    int nx = x + di[0] * i, ny = y + di[1] * i;
                    if (nx < 0 || nx >= n || ny < 0 || ny >= m) break;
                    if (g[nx].charAt(ny) == '#') break;
                    if (dfs(nx, ny, p, q, k + 1) == 0) return f[state][k] = 0;
                }
            }
            return f[state][k] = 1;
        } else { // cat
            for (int[] di : dirs) {
                for (int i = 0; i <= a; i++) {
                    int np = p + di[0] * i, nq = q + di[1] * i;
                    if (np < 0 || np >= n || nq < 0 || nq >= m) break;
                    if (g[np].charAt(nq) == '#') break;
                    if (dfs(x, y, np, nq, k + 1) == 1) return f[state][k] = 1;
                }
            }
            return f[state][k] = 0;
        }
    }
    public boolean canMouseWin(String[] grid, int catJump, int mouseJump) {
        g = grid;
        n = g.length; m = g[0].length(); a = catJump; b = mouseJump;
        for (int i = 0; i < S; i++) Arrays.fill(f[i], -1);
        int x = 0, y = 0, p = 0, q = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (g[i].charAt(j) == 'M') {
                    x = i; y = j;
                } else if (g[i].charAt(j) == 'C') {
                    p = i; q = j;
                } else if (g[i].charAt(j) == 'F') {
                    tx = i; ty = j;
                }
            }
        }
        return dfs(x, y, p, q, 0) == 0;
    }
}