A game on an undirected graph is played by two players, Mouse and Cat, who alternate turns.
The graph is given as follows: graph[a] is a list of all nodes b such that ab is an edge of the graph.
The mouse starts at node 1 and goes first, the cat starts at node 2 and goes second, and there is a hole at node 0.
During each player's turn, they must travel along one edge of the graph that meets where they are. For example, if the Mouse is at node 1, it must travel to any node in graph[1].
Additionally, it is not allowed for the Cat to travel to the Hole (node 0.)
Then, the game can end in three ways:
- If ever the Cat occupies the same node as the Mouse, the Cat wins.
- If ever the Mouse reaches the Hole, the Mouse wins.
- If ever a position is repeated (i.e., the players are in the same position as a previous turn, and it is the same player's turn to move), the game is a draw.
Given a graph, and assuming both players play optimally, return
1if the mouse wins the game,2if the cat wins the game, or0if the game is a draw.
Example 1:
Input: graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]] Output: 0
Example 2:
Input: graph = [[1,3],[0],[3],[0,2]] Output: 1
Constraints:
3 <= graph.length <= 501 <= graph[i].length < graph.length0 <= graph[i][j] < graph.lengthgraph[i][j] != igraph[i]is unique.- The mouse and the cat can always move.
class Solution:
def catMouseGame(self, graph: List[List[int]]) -> int:
@cache
def dfs(i, j, k):
# mouse / cat / steps
if k >= 2 * len(graph):
return 0 # tie
if i == 0:
return 1 # mouse wins
if i == j:
return 2 # cat wins
if k % 2: # cat’s turn
tie = False
for next in graph[j]:
if next == 0:
continue
x = dfs(i, next, k + 1)
if x == 2:
return 2
if x == 0:
# continue to find if exists winning case
tie = True
if tie:
return 0
return 1
else: # mouse's turn
tie = False
for next in graph[i]:
x = dfs(next, j, k + 1)
if x == 1:
return 1
if x == 0:
# continue to find if exists winning case
tie = True
if tie:
return 0
return 2
return dfs(1, 2, 0)class Solution {
private int[][][] memo;
private int[][] graph;
public int catMouseGame(int[][] graph) {
int n = graph.length;
this.graph = graph;
memo = new int[n][n][2 * n + 10];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
for (int k = 0; k < 2 * n + 10; ++k) {
memo[i][j][k] = -1;
}
}
}
return dfs(1, 2, 0);
}
private int dfs(int i, int j, int k) {
// mouse / cat / steps
if (memo[i][j][k] != -1) {
return memo[i][j][k];
}
if (k >= 2 * graph.length) {
// tie
memo[i][j][k] = 0;
} else if (i == 0) {
// mouse wins
memo[i][j][k] = 1;
} else if (i == j) {
// cat wins
memo[i][j][k] = 2;
} else if (k % 2 == 1) {
// cat's turn
boolean tie = false;
boolean win = false;
for (int next : graph[j]) {
if (next == 0) {
continue;
}
int x = dfs(i, next, k + 1);
if (x == 2) {
win = true;
memo[i][j][k] = 2;
break;
}
if (x == 0) {
// continue to find if exists winning case
tie = true;
}
}
if (!win) {
memo[i][j][k] = tie ? 0 : 1;
}
} else {
// mouse's turn
boolean tie = false;
boolean win = false;
for (int next : graph[i]) {
int x = dfs(next, j, k + 1);
if (x == 1) {
win = true;
memo[i][j][k] = 1;
break;
}
if (x == 0) {
// continue to find if exists winning case
tie = true;
}
}
if (!win) {
memo[i][j][k] = tie ? 0 : 2;
}
}
return memo[i][j][k];
}
}class Solution {
public:
vector<vector<vector<int>>> memo;
vector<vector<int>> graph;
int catMouseGame(vector<vector<int>>& graph) {
int n = graph.size();
this->graph = graph;
memo.resize(n, vector<vector<int>>(n, vector<int>(2 * n + 10, -1)));
return dfs(1, 2, 0);
}
int dfs(int i, int j, int k) {
if (memo[i][j][k] != -1) return memo[i][j][k];
if (k >= 2 * graph.size())
memo[i][j][k] = 0;
else if (i == 0)
memo[i][j][k] = 1;
else if (i == j)
memo[i][j][k] = 2;
else if (k % 2) {
bool tie = false, win = false;
for (int next : graph[j]) {
if (next == 0) continue;
int x = dfs(i, next, k + 1);
if (x == 2) {
win = true;
memo[i][j][k] = 2;
break;
}
if (x == 0) tie = true;
}
if (!win) memo[i][j][k] = tie ? 0 : 1;
} else {
bool tie = false, win = false;
for (int next : graph[i]) {
int x = dfs(next, j, k + 1);
if (x == 1) {
win = true;
memo[i][j][k] = 1;
break;
}
if (x == 0) tie = true;
}
if (!win) memo[i][j][k] = tie ? 0 : 2;
}
return memo[i][j][k];
}
};func catMouseGame(graph [][]int) int {
n := len(graph)
memo := make([][][]int, n)
for i := range memo {
memo[i] = make([][]int, n)
for j := range memo[i] {
memo[i][j] = make([]int, 2*n+10)
for k := range memo[i][j] {
memo[i][j][k] = -1
}
}
}
var dfs func(i, j, k int) int
dfs = func(i, j, k int) int {
if memo[i][j][k] != -1 {
return memo[i][j][k]
}
if k >= 2*len(graph) {
memo[i][j][k] = 0
} else if i == 0 {
memo[i][j][k] = 1
} else if i == j {
memo[i][j][k] = 2
} else if k%2 == 1 {
tie, win := false, false
for _, next := range graph[j] {
if next == 0 {
continue
}
x := dfs(i, next, k+1)
if x == 2 {
win = true
memo[i][j][k] = 2
break
}
if x == 0 {
tie = true
}
}
if !win {
if tie {
memo[i][j][k] = 0
} else {
memo[i][j][k] = 1
}
}
} else {
tie, win := false, false
for _, next := range graph[i] {
x := dfs(next, j, k+1)
if x == 1 {
win = true
memo[i][j][k] = 1
break
}
if x == 0 {
tie = true
}
}
if !win {
if tie {
memo[i][j][k] = 0
} else {
memo[i][j][k] = 2
}
}
}
return memo[i][j][k]
}
return dfs(1, 2, 0)
}