# Участник:Larin.dv/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;
}
}
}
};```