Sponsored
Sponsored
This approach uses dynamic programming with a 3D array to store the results for each game state. We use the state (mouse and cat positions, and the current turn) to determine the game's outcome. This helps us avoid redundant computations and efficiently reach a solution through recursive calls. Each possible state is evaluated based on whether the mouse or cat can win from that point, or if it's a draw.
Time Complexity: O(N^3), where N is the number of graph nodes, since we try each node for mouse, cat, and turns.
Space Complexity: O(N^2), owing to storage in the DP table.
1def catMouseGame(graph):
2 N = len(graph)
3 DRAW, MOUSE, CAT = 0, 1, 2
4 state = [[[DRAW] * N for _ in range(N)] for _ in range(2 * N)]
5
6 for i in range(N):
7 for t in range(2 * N):
8 state[t][i][i] = CAT
9 state[t][0][i] = MOUSE
10
11 def can_mouse_win(t, mouse, cat):
12 if t == 2 * N or state[t][mouse][cat] != DRAW:
13 return state[t][mouse][cat]
14
15 if t % 2 == 0:
16 result = CAT
17 for next_mouse in graph[mouse]:
18 if next_mouse == cat:
19 continue
20 if can_mouse_win(t + 1, next_mouse, cat) == MOUSE:
21 result = MOUSE
22 break
23 elif can_mouse_win(t + 1, next_mouse, cat) == DRAW:
24 result = DRAW
25 state[t][mouse][cat] = result
26 else:
27 result = MOUSE
28 for next_cat in graph[cat]:
29 if next_cat == 0:
30 continue
31 if can_mouse_win(t + 1, mouse, next_cat) == CAT:
32 result = CAT
33 break
34 elif can_mouse_win(t + 1, mouse, next_cat) == DRAW:
35 result = DRAW
36 state[t][mouse][cat] = result
37
38 return state[t][mouse][cat]
39
40 return can_mouse_win(0, 1, 2)This approach uses a breadth-first search (BFS) combined with memoization to handle game states. We use a queue to systematically explore potential moves for both the mouse and cat, updating states based on the outcomes of previous states. This approach effectively captures the transitions and dependencies among various game states, systematically moving towards an outcome.
Time Complexity: O(N^3), as each state must be iterated for mouse, cat and move number combinations.
Space Complexity: O(N^2), due to storing states in the DP table with a queue usage.
1from collections import deque
2
3def catMouseGame(graph):
4
This approach is based on a recursive minimax algorithm with memoization to optimize overlapping subproblems. We represent the game state as a triplet (mouse_position, cat_position, turn), and use memoization to store results of states that have been computed before.
Each state evaluates its possible next states recursively, calculating whether it's a guaranteed win, loss, or draw from that position.
Time Complexity: O(n^3) - In the worst case, each state (mouse position, cat position, turn) is visited once for every player due to memoization.
Space Complexity: O(n^2) - Space used by the memoization cache, capturing every unique state evaluated.
1from functools import lru_cache
2
3
This approach uses a breadth-first search (BFS) method in which we 'color' the nodes based on current positions and outcomes as we traverse the graph. This approach focuses on evaluating the nodes with terminal states quickly and propagating results efficiently to neighbors. The 'coloring' means marking nodes with direct results like wins or losses and progressively marking draws as paths are evaluated.
Time Complexity: O(n^3) - BFS explores states by all node combinations leading to exhaustive evaluations, ensuring each is processed to fixed evaluation.
Space Complexity: O(n^2) - Each node stores multiple state outcomes efficiently within a moderate space allocation.
1public class Solution {
2 public int CatMouseGame(int[][] graph) {
3 int n = graph.Length;
4 int[,] dp = new int[n, n, 2 * n];
Queue<int[]> queue = new Queue<int[]>();
const int DRAW = 0, MOUSE_WIN = 1, CAT_WIN = 2;
for (int i = 0; i < n; i++) {
for (int t = 0; t < 2 * n; t++) {
dp[0, i, t] = MOUSE_WIN;
dp[i, i, t] = CAT_WIN;
}
}
for (int t = 0; t < 2 * n; t++) {
for (int m = 0; m < n; m++) {
for (int c = 0; c < n; c++) {
if (dp[m, c, t] != DRAW) continue;
if (t % 2 == 0) { // Mouse's turn
foreach (int mv in graph[m]) {
if (dp[mv, c, t + 1] == MOUSE_WIN) {
dp[m, c, t] = MOUSE_WIN;
queue.Enqueue(new int[] { m, c, t });
break;
}
}
} else { // Cat's turn
foreach (int cv in graph[c]) {
if (cv == 0) continue;
if (dp[m, cv, t + 1] == CAT_WIN) {
dp[m, c, t] = CAT_WIN;
queue.Enqueue(new int[] { m, c, t });
break;
}
}
}
}
}
}
while (queue.Count > 0) {
var arr = queue.Dequeue();
int m = arr[0], c = arr[1], t = arr[2];
if (t == 0) continue;
int prevT = t - 1;
foreach (int pm in graph[m]) {
if (dp[pm, c, prevT] == DRAW) {
if ((t % 2 == 0 && dp[m, c, t] == MOUSE_WIN) || (t % 2 == 1 && dp[m, c, t] == CAT_WIN)) {
dp[pm, c, prevT] = dp[m, c, t];
queue.Enqueue(new int[] { pm, c, prevT });
}
}
}
}
return dp[1, 2, 0];
}
}This Python solution uses a recursive function with memoization (via lru_cache) to decide the outcome at each state. The base states evaluate whether the mouse wins (reaches 0), the cat wins (occupies the same node as the mouse), or if the number of turns suggests a draw. Depending on whether it's the mouse's or cat's turn, the function iterates over possible moves, recursively determining and memorizing possible outcomes. The solution makes use of depth-first exploration to optimize using previously computed states.
In C#, the use of a queue to manage iterative state evaluation is preferred due to the ease of managing expressed parallel sequences of outcomes. The dp array is a tabulation method to pre-calculate win/draw outcomes for various states. BFS ensures that the calculations are pushed back efficiently, relying on pre-determined optimal outcomes in a similar manner to memoization without recursion. This stably supports performance across depth requirements through iteration.