https://leetcode.com/problems/cat-and-mouse/description/

913-cat-and-mouse.py

# Time: O(N^3) 
# where n is the number of nodes in the graph. 
# There are O(N^2) states, and each state has an outdegree of N, as there are at most N different moves.
# Space: O(N^2)

class Solution:
    def catMouseGame(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: int
        """
        self.graph = graph 
        self.memo = {}
        return self.move(2, 1, True)
        
    def move(self, cat, mouse, m_turn):
        key = (cat, mouse, m_turn)
        if key in self.memo:
            return self.memo[key]
        self.memo[key] = 0
        
        if m_turn:
            return self.mouse_play(key, cat, mouse, m_turn)
        else:
            return self.cat_play(key, cat, mouse, m_turn)
        
    def mouse_play(self, key, cat, turn, m_turn):
        # base case 
        for nxt in self.graph[turn]:
            if nxt == 0:
                self.memo[key] = 1
                return 1
        
        res = 2
        for nxt in self.graph[turn]:
            if nxt == cat:
                continue 
            tmp = self.move(cat, nxt, False)
            if tmp == 1:
                res = 1
                break
            if tmp == 0:
                res = 0
        self.memo[key] = res 
        return res 
    
    def cat_play(self, key, turn, mouse, m_turn):
        # base case 
        for nxt in self.graph[turn]:
            if nxt == mouse:
                self.memo[key] = 2
                return 2
            
        res = 1 
        for nxt in self.graph[turn]:
            if nxt ==0:
                continue 
            tmp = self.move(nxt, mouse, True)
            if tmp == 2:
                res = 2
                break 
            if tmp == 0:
                res = 0
        self.memo[key] = res 
        return res