Tom and Jerry's Graph Chase Medium · Graph, Game Theory, BFS, Minimax · ZipHQ · Hints: A state in the game consists of both players' positions and whose turn it is next. To guarantee capture, Tom must have a strategy that leads to capture regardless of Jerry's choices.
You are given an undirected graph with n vertices labeled from 0 to n-1 and a list of edges. Tom and Jerry start at vertices tom and jerry respectively. The game proceeds in seconds. At each second, Jerry moves first: he either stays at his current vertex or moves to an adjacent vertex (one connected by an edge). Then Tom moves: he also either stays or moves to an adjacent vertex. If at any moment Tom and Jerry occupy the same vertex, Jerry is caught and the game ends.
Tom aims to minimize the time to capture, while Jerry aims to maximize it (or evade indefinitely). Both play optimally with full knowledge of the graph and each other's positions. We need to find the minimum number of seconds that Tom can guarantee capture, assuming Jerry plays to delay as much as possible. If Jerry can avoid capture forever, return -1.
If Tom and Jerry start at the same vertex, the game ends immediately and we return 0. Otherwise, capture during the first second (either during Jerry's move or Tom's move) counts as time 1.
Write a function guaranteed_capture_time(n: int, edges: List[List[int]], tom: int, jerry: int) -> int that returns the guaranteed capture time or -1.
Example 1:
Input: n = 4, edges = [[0,1],[1,2],[2,3]], tom = 0, jerry = 3
Output: 3
Explanation: The graph is a path of four vertices. Tom and Jerry are at opposite ends. With optimal play, Jerry can delay capture until the third second, but Tom can guarantee capture by that time.
Example 2:
Input: n = 4, edges = [[0,1],[1,2],[2,3],[3,0]], tom = 1, jerry = 3
Output: -1
Explanation: The graph is a cycle of four vertices. Tom and Jerry start at opposite vertices. Jerry can always move to maintain an even distance, evading capture indefinitely.
Example 3:
Input: n = 4, edges = [[0,1],[2,3]], tom = 0, jerry = 2
Output: -1
Explanation: Tom and Jerry are in different connected components. There is no path between them, so Tom can never catch Jerry.
Constraints:
1 <= n <= 600 <= tom, jerry < nedges contains no duplicate edges and each edge is an undirected pair [u, v] with 0 <= u, v < n and u != v.