题目
image.pngimage.pngimage.png

解题代码

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