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.

Mouse starts at node 1 and goes first, 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 3 ways:

Given a graph, and assuming both players play optimally, return 1 if the game is won by Mouse, 2 if the game is won by Cat, and 0 if the game is a draw.

 


Example 1:

Input: [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
Output: 0
Explanation:
4---3---1
|   |
2---5
 \ /
  0

 

Note:

  1. 3 <= graph.length <= 50
  2. It is guaranteed that graph[1] is non-empty.
  3. It is guaranteed that graph[2] contains a non-zero element. 

Solution:

class Solution {
    /*
        Let's say that if mouse succeeds we return 1.
        If cat succeds we return -1.
        If we have draw, then 0.

        So we can apply this knowledge to minimax approach.
        If it's mouse turn -> we're trying to maximize, otherwise we're trying to minimize.
        Small trick is that we return 0, when number of turns == graph.length * 2, since we have graph.length positions and each position visited twice (by cat or mouse).
    */  
    public int catMouseGame(int[][] graph) {
        int n = graph.length;
        int res = helper(graph, 2, 1, 0, new Integer[n][n][n * 2]);
        return res == -1 ? 2 : res;
    }
    
    private int helper(int[][] graph, int cat, int mouse, int turn, Integer[][][] dp) {
        if (cat == mouse) return -1;
        if (mouse == 0) return 1;
        if (turn == graph.length * 2) return 0;
        if (dp[cat][mouse][turn] != null) return dp[cat][mouse][turn];
        int res = turn % 2 == 0 ? -1 : 1;
        if (turn % 2 == 0) {
            for (int i : graph[mouse]) {
                res = Math.max(res, helper(graph, cat, i, turn + 1, dp));
            }
        } else {
            for (int i : graph[cat]) {
                if (i == 0) continue;
                res = Math.min(res, helper(graph, i, mouse, turn + 1, dp));
            }
        }
        
        dp[cat][mouse][turn] = res;
        return res;
    }
}