Practice/Google/Leetcode 913. Cat and Mouse

Leetcode 913. Cat and Mouse

CodingMust

Problem

A rabbit and a fox are playing a game on an undirected graph. The graph has n nodes numbered from 0 to n-1, and the edges are given as an adjacency list where graph[i] contains all nodes adjacent to node i.

Game Rules:

• The rabbit starts at node 1 and moves first
• The fox starts at node 2 and moves second
• Players alternate turns, moving to an adjacent node along an edge
• The fox cannot enter node 0 (the rabbit's burrow)
• The rabbit wins if it reaches node 0
• The fox wins if it lands on the same node as the rabbit
• If the same game state (rabbit position, fox position, whose turn) occurs more than once, the game is a draw

Both players play optimally to achieve the best outcome for themselves (rabbit wants to win > draw > lose, fox wants to win > draw > lose).

Return:

• 0 if the rabbit wins
• 1 if the game is a draw
• 2 if the fox wins

Requirements

1. Determine the outcome of the game when both players play optimally
2. Handle all possible game states including winning, losing, and draw scenarios
3. Account for cycles that lead to repeated game states
4. Correctly model the constraint that the fox cannot enter node 0

Constraints

• 3 <= n <= 50
• 1 < graph[i].length <= n
• 0 <= graph[i][j] < n
• graph[i][j] are all unique
• The graph is undirected (if j is in graph[i], then i is in graph[j])
• The graph is connected
• Node 0 is the rabbit's burrow (fox cannot enter)
• Rabbit starts at node 1, fox starts at node 2

Examples

Example 1:

Input: graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]] Output: 0 Explanation: The rabbit can reach node 0 before the fox catches it. From node 1, the rabbit moves to node 3, then the fox moves to node 5, then the rabbit can reach node 0 through optimal path selection.

Example 2:

Input: graph = [[1,3],[0],[3],[0,2]] Output: 2 Explanation: The fox can catch the rabbit. The rabbit is at node 1, fox at node 2. After any move by the rabbit, the fox can position itself to eventually catch the rabbit before it reaches node 0.

Example 3:

Input: graph = [[2,3],[3,4],[0,4],[0,1],[1,2]] Output: 1 Explanation: The game results in a draw. Both players can maneuver to avoid losing but neither can force a win, leading to repeated positions.