{x}
blog image

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. 

913. Cat and Mouse

This problem describes a game played on a graph between a mouse and a cat. The goal is to determine the outcome of the game assuming both players play optimally.

Problem Description:

  • An undirected graph is represented by an adjacency list graph.
  • The mouse starts at node 1, the cat at node 2, and there's a hole at node 0.
  • Players alternate turns, moving along one edge at a time.
  • The cat cannot move to the hole.
  • The game ends if:
    • The cat and mouse occupy the same node (cat wins).
    • The mouse reaches the hole (mouse wins).
    • A position is repeated (draw).

Solution Approach (Topological Sort based DP):

The solution uses a dynamic programming approach with topological sorting principles to efficiently determine the game's outcome. We represent the game state as a tuple (mouse_pos, cat_pos, turn). The core idea is to work backwards from terminal states (win/loss for either player) to determine the outcome of earlier states.

  1. Base Cases:

    • If mouse_pos == cat_pos, the cat wins (CAT_WIN).
    • If mouse_pos == 0, the mouse wins (MOUSE_WIN).

  2. Recursive Relation: For each state (m, c, t), we consider possible previous states:

    • If t == MOUSE_TURN: The cat's position c remains the same, and the mouse moves from one of the neighbors of m to m.
    • If t == CAT_TURN: The mouse's position m remains the same, and the cat moves from one of the neighbors of c (excluding the hole) to c.

  3. Dynamic Programming: We use a 3D array ans[m][c][t] to store the outcome (MOUSE_WIN, CAT_WIN, or TIE) for each state. We start by initializing the base cases. Then, iteratively, for each state, we check the outcomes of its possible previous states. The logic is:

    • If a previous state leads to a win for the current player, that previous state is also a win.
    • If all previous states for a player lead to a loss, then that state is a loss for that player.

  4. Topological Sort (Implicit): The iterative process implicitly performs a topological sort, ensuring that we always process states before their preceding states. We use a queue to manage states that need to be processed.

  5. Degree Calculation: A degree array tracks how many possible moves exist from each state. This helps to determine when all possible previous states for a player have been checked. When the degree for a state becomes 0, it means all preceding states have been processed.

  6. Return Value: Finally, ans[MOUSE_START][CAT_START][MOUSE_TURN] provides the outcome of the game starting from the initial positions.

Time Complexity: O(N^3), where N is the number of nodes in the graph. This is because we iterate through all possible states (N x N x 2).

Space Complexity: O(N^3) to store the ans and degree arrays.

(Code examples are provided in the original response. Refer to the Python, Java, C++, Go, TypeScript, and C# code snippets for implementation details.)