Readable Python Solution


  • 0
    K
    class Solution:
        def knightProbability(self, N, K, r, c):
            
            from collections import defaultdict
            prob_cache = defaultdict(int) 
            
            def prob_stays_on_board(n, k, r, c):
                if r < 0 or c < 0 or r >= n or c >=n :
                    return 0
                if k == 0:
                    return 1.0
                if (n, k, r, c) in prob_cache:
                    return prob_cache[(n,k,r,c)]
                
                new_params = [(n, k - 1, r - i, c - j) for i, j
                              in [(2, 1), (2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2), (-2, 1), (-2, -1)]]
                
                for param in new_params:
                    prob_cache[(n, k, r, c)] += prob_stays_on_board(*param)/8.0
                
                
                return prob_cache[(n, k, r, c)]
            
            
            return prob_stays_on_board(n=N, k=K, r=r, c=c)
                    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.