C++; top-down; symmetry exploitation


  • 0
    D

    Exploit symmetry by creating probability library for only quarter of chess board:

    class Solution 
    {
        unordered_map<int, double> d_lib;
    	
        public:
            double knightProbability(int N, int K, int r, int c) 
            {	
                // exploit symmetry:
                if (r > (N - 1) / 2)
                    r = (N - 1) - r;
    
                if (c > (N - 1) / 2)
                    c = (N - 1) - c;			
    
                if (r < 0 || c < 0)
                    return 0;			
    			
                if (K == 0)
                    return 1;
    			
                int key = N * r + c + 1000 * K;	
                unordered_map<int, double>::iterator it = d_lib.find(key);
                if (it != d_lib.end())
                    return it->second;
    				
                double prob = 0.125 * knightProbability(N, K - 1, r - 2, c - 1) +  
                              0.125 * knightProbability(N, K - 1, r - 2, c + 1) +  	
                              0.125 * knightProbability(N, K - 1, r + 2, c - 1) +  	
                              0.125 * knightProbability(N, K - 1, r + 2, c + 1) +  	
                              0.125 * knightProbability(N, K - 1, r - 1, c - 2) +  	
                              0.125 * knightProbability(N, K - 1, r - 1, c + 2) +  	
                              0.125 * knightProbability(N, K - 1, r + 1, c - 2) +  	
                              0.125 * knightProbability(N, K - 1, r + 1, c + 2);
    
                d_lib[key] = prob;
    						  
                return prob;
            }
    };
    
    

Log in to reply
 

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