题目

类型：动态规划
image.png

解题思路

image.png

代码

  1. class Solution {
  2.     static int N = 55;
  3.     static int[][][] f = new int[2 * N * N][N][N];
  4.     int[][] g;
  5.     int n;
  6.     public int catMouseGame(int[][] graph) {
  7.         g = graph;
  8.         n = g.length;
  9.         for (int k = 0; k < 2 * n * n; k++) {
  10.             for (int i = 0; i < n; i++) {
  11.                 for (int j = 0; j < n; j++) {
  12.                     f[k][i][j] = -1;
  13.                 }
  14.             }
  15.         }
  16.         return dfs(0, 1, 2);
  17.     }
  18.     // 0:draw / 1:mouse / 2:cat
  19.     int dfs(int k, int a, int b) {
  20.         int ans = f[k][a][b];
  21.         if (a == 0) ans = 1;
  22.         else if (a == b) ans = 2;
  23.         else if (k >= 2 * n * n) ans = 0;
  24.         else if (ans == -1) {
  25.             if (k % 2 == 0) { // mouse
  26.                 boolean win = false, draw = false;
  27.                 for (int ne : g[a]) {
  28.                     int t = dfs(k + 1, ne, b);
  29.                     if (t == 1) win = true;
  30.                     else if (t == 0) draw = true;
  31.                     if (win) break;
  32.                 }
  33.                 if (win) ans = 1;
  34.                 else if (draw) ans = 0;
  35.                 else ans = 2;
  36.             } else { // cat
  37.                 boolean win = false, draw = false;
  38.                 for (int ne : g[b]) {
  39.                     if (ne == 0) continue;
  40.                     int t = dfs(k + 1, a, ne);
  41.                     if (t == 2) win = true;
  42.                     else if (t == 0) draw = true;
  43.                     if (win) break;
  44.                 }
  45.                 if (win) ans = 2;
  46.                 else if (draw) ans = 0;
  47.                 else ans = 1;
  48.             }
  49.         }
  50.         f[k][a][b] = ans;
  51.         return ans;
  52.     }
  53. }