0 to n - 1, and halls[a] lists the halls connected to hall a by a passage. Hall 0 is the exit to the street.
The thief starts in hall 1 and the guard in hall 2. They take turns, the thief first. A move means walking through one passage into an adjacent hall; staying put is not allowed. The guard may never enter hall 0.
The game ends as soon as:
- the guard and the thief are in the same hall: the guard wins;
- the thief reaches hall 0: the thief wins;
- a position repeats, with both standing where they once stood before and the same player to move: it is a draw.
Both play optimally. Return 1 if the thief wins, 2 if the guard wins, and 0 for a draw.halls=[[1], [0, 2], [1]] → 1
The thief is in hall 1 right next to the exit 0, so he leaves on his very first move.
halls=[[3], [2], [1, 3], [0, 2]] → 2
From hall 1 the thief can only step into hall 2, where the guard is standing, and gets caught at once.
halls=[[3], [3, 4], [3, 4], [0, 1, 2], [1, 2]] → 2
b is in halls[a], then a is in halls[b]halls=[[1], [0, 2], [1]]
1
Run checks the first 3 tests in your browser. Submit checks all 45 tests on the server, hidden ones included.