913. Cat and Mouse LeetCode Solution
In this guide, you will get 913. Cat and Mouse LeetCode Solution with the best time and space complexity. The solution to Cat and Mouse problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Cat and Mouse solution in C++
- Cat and Mouse solution in Java
- Cat and Mouse solution in Python
- Additional Resources
Problem Statement of Cat and Mouse
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
1 if the mouse wins the game,
2 if the cat wins the game, or
0 if 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 <= 50
1 <= graph[i].length < graph.length
0 <= graph[i][j] < graph.length
graph[i][j] != i
graph[i] is unique.
The mouse and the cat can always move.
Complexity Analysis
- Time Complexity: O(n^3)
- Space Complexity: O(n^3)
913. Cat and Mouse LeetCode Solution in C++
enum class State { kDraw, kMouseWin, kCatWin };
class Solution {
public:
int catMouseGame(vector<vector<int>>& graph) {
const int n = graph.size();
// result of (cat, mouse, move)
// move := 0 (mouse) / 1 (cat)
vector<vector<vector<State>>> states(
n, vector<vector<State>>(n, vector<State>(2)));
vector<vector<vector<int>>> outDegree(
n, vector<vector<int>>(n, vector<int>(2)));
queue<tuple<int, int, int, State>> q; // (cat, mouse, move, state)
for (int cat = 0; cat < n; ++cat)
for (int mouse = 0; mouse < n; ++mouse) {
outDegree[cat][mouse][0] = graph[mouse].size();
outDegree[cat][mouse][1] =
graph[cat].size() - ranges::count(graph[cat], 0);
}
// Start from the states s.t. the winner can be determined.
for (int cat = 1; cat < n; ++cat)
for (int move = 0; move < 2; ++move) {
// Mouse is in the hole.
states[cat][0][move] = State::kMouseWin;
q.emplace(cat, 0, move, State::kMouseWin);
// Cat catches mouse.
states[cat][cat][move] = State::kCatWin;
q.emplace(cat, cat, move, State::kCatWin);
}
while (!q.empty()) {
const auto [cat, mouse, move, state] = q.front();
q.pop();
if (cat == 2 && mouse == 1 && move == 0)
return static_cast<int>(state);
const int prevMove = move ^ 1;
for (const int prev : graph[prevMove ? cat : mouse]) {
const int prevCat = prevMove ? prev : cat;
if (prevCat == 0) // invalid
continue;
const int prevMouse = prevMove ? mouse : prev;
// The state has been determined.
if (states[prevCat][prevMouse][prevMove] != State::kDraw)
continue;
if (prevMove == 0 && state == State::kMouseWin ||
prevMove == 1 && state == State::kCatWin ||
--outDegree[prevCat][prevMouse][prevMove] == 0) {
states[prevCat][prevMouse][prevMove] = state;
q.emplace(prevCat, prevMouse, prevMove, state);
}
}
}
return static_cast<int>(states[2][1][0]);
}
};
/* code provided by PROGIEZ */913. Cat and Mouse LeetCode Solution in Java
enum State { kDraw, kMouseWin, kCatWin }
class Solution {
public int catMouseGame(int[][] graph) {
final int n = graph.length;
// result of (cat, mouse, move)
// move := 0 (mouse) / 1 (cat)
int[][][] states = new int[n][n][2];
int[][][] outDegree = new int[n][n][2];
Queue<int[]> q = new ArrayDeque<>();
for (int cat = 0; cat < n; ++cat)
for (int mouse = 0; mouse < n; ++mouse) {
outDegree[cat][mouse][0] = graph[mouse].length;
outDegree[cat][mouse][1] =
graph[cat].length - (Arrays.stream(graph[cat]).anyMatch(v -> v == 0) ? 1 : 0);
}
// Start from the states s.t. the winner can be determined.
for (int cat = 1; cat < n; ++cat)
for (int move = 0; move < 2; ++move) {
// Mouse is in the hole.
states[cat][0][move] = State.kMouseWin.ordinal();
q.offer(new int[] {cat, 0, move, State.kMouseWin.ordinal()});
// Cat catches mouse.
states[cat][cat][move] = State.kCatWin.ordinal();
q.offer(new int[] {cat, cat, move, State.kCatWin.ordinal()});
}
while (!q.isEmpty()) {
final int cat = q.peek()[0];
final int mouse = q.peek()[1];
final int move = q.peek()[2];
final int state = q.poll()[3];
if (cat == 2 && mouse == 1 && move == 0)
return state;
final int prevMove = move ^ 1;
for (final int prev : graph[prevMove == 0 ? mouse : cat]) {
final int prevCat = prevMove == 0 ? cat : prev;
if (prevCat == 0) // invalid
continue;
final int prevMouse = prevMove == 0 ? prev : mouse;
// The state has been determined.
if (states[prevCat][prevMouse][prevMove] > 0)
continue;
if (prevMove == 0 && state == State.kMouseWin.ordinal() ||
prevMove == 1 && state == State.kCatWin.ordinal() ||
--outDegree[prevCat][prevMouse][prevMove] == 0) {
states[prevCat][prevMouse][prevMove] = state;
q.offer(new int[] {prevCat, prevMouse, prevMove, state});
}
}
}
return states[2][1][0];
}
}
// code provided by PROGIEZ913. Cat and Mouse LeetCode Solution in Python
from enum import IntEnum
class State(IntEnum):
kDraw = 0
kMouseWin = 1
kCatWin = 2
class Solution:
def catMouseGame(self, graph: list[list[int]]) -> int:
n = len(graph)
# result of (cat, mouse, move)
# move := 0 (mouse) // 1 (cat)
states = [[[0] * 2 for _ in range(n)] for _ in range(n)]
outDegree = [[[0] * 2 for _ in range(n)] for _ in range(n)]
q = collections.deque() # (cat, mouse, move, state)
for cat in range(n):
for mouse in range(n):
outDegree[cat][mouse][0] = len(graph[mouse])
outDegree[cat][mouse][1] = len(graph[cat]) - graph[cat].count(0)
# Start from the states s.t. the winner can be determined.
for cat in range(1, n):
for move in range(2):
# Mouse is in the hole.
states[cat][0][move] = int(State.kMouseWin)
q.append((cat, 0, move, int(State.kMouseWin)))
# Cat catches mouse.
states[cat][cat][move] = int(State.kCatWin)
q.append((cat, cat, move, int(State.kCatWin)))
while q:
cat, mouse, move, state = q.popleft()
if cat == 2 and mouse == 1 and move == 0:
return state
prevMove = move ^ 1
for prev in graph[cat if prevMove else mouse]:
prevCat = prev if prevMove else cat
if prevCat == 0: # invalid
continue
prevMouse = mouse if prevMove else prev
# The state has been determined.
if states[prevCat][prevMouse][prevMove]:
continue
if (prevMove == 0 and state == int(State.kMouseWin) or
prevMove == 1 and state == int(State.kCatWin)):
states[prevCat][prevMouse][prevMove] = state
q.append((prevCat, prevMouse, prevMove, state))
else:
outDegree[prevCat][prevMouse][prevMove] -= 1
if outDegree[prevCat][prevMouse][prevMove] == 0:
states[prevCat][prevMouse][prevMove] = state
q.append((prevCat, prevMouse, prevMove, state))
return states[2][1][0]
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.