Участник:Larin.dv/Cat and Mouse

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/cat-and-mouse/

class Solution {
public:
  int catMouseGame(vector<vector<int>> &graph) {
    const int n = graph.size();
 
    f_ = vector<vector<vector<int>>>(
        2 * n, vector<vector<int>>(n, vector<int>(n, -1)));
    return solve(graph, 0, 1, 2);
  }
 
private:
  vector<vector<vector<int>>> f_;
 
  int solve(vector<vector<int>> &graph, int t, int x, int y) {
    if (t == graph.size() * 2) {
      return 0;
    }
    if (x == y) {
      return f_[t][x][y] = 2;
    }
    if (x == 0) {
      return f_[t][x][y] = 1;
    }
    if (f_[t][x][y] != -1) {
      return f_[t][x][y];
    }
    int who = t % 2;
    if (who == 0) {
      bool cat_can_win = true;
      for (int i = 0; i < graph[x].size(); i++) {
        int nxt = solve(graph, t + 1, graph[x][i], y);
        if (nxt == 1) {
          return f_[t][x][y] = 1;
        } else if (nxt != 2) {
          cat_can_win = false;
        }
      }
 
      if (cat_can_win) {
        return f_[t][x][y] = 2;
      } else {
        return f_[t][x][y] = 0;
      }
    } else {
      bool mouse_can_win = true;
      for (int i = 0; i < graph[y].size(); i++) {
        if (graph[y][i] != 0) {
          int nxt = solve(graph, t + 1, x, graph[y][i]);
          if (nxt == 2) {
            return f_[t][x][y] = 2;
          } else if (nxt != 1) {
            mouse_can_win = false;
          }
        }
      }
      if (mouse_can_win) {
        return f_[t][x][y] = 1;
      } else {
        return f_[t][x][y] = 0;
      }
    }
  }
};