C++ clear DFS with memorization


  • 0
    L
    class Solution {
    public:
        double knightProbability(int N, int K, int r, int c) {
            int remain = K;
            int start_r = r;
            int start_c = c;
            double ret = dfs(start_r, start_c, remain, N);
            return ret;
        }
        
        
    private:
        
        bool isValid(int r, int c, int N)
        {
            return r >= 0 && r < N && c >= 0 && c < N;
        }
        
        double dfs(int r, int c, int remain, int N)
        {
            static vector<pair<int, int> > dirs = 
            {
                {2, 1},
                {2, -1},
                {-2, 1},
                {-2, -1},
                {1, 2},
                {1, -2},
                {-1, 2},
                {-1, -2}
            };
            
            if(isValid(r, c, N) == false)
            {
                return 0.0;
            }
            
            if(remain == 0)
            {
                return 1.0;
            }
            
            int key = getKey(r, c, remain);
            if(cache.find(key) != cache.end())
            {
                return cache[key];
            }
            
            double p = 0.0;
            for(auto dir : dirs)
            {
                int next_r = r + dir.first;
                int next_c = c + dir.second;
                p += dfs(next_r, next_c, remain - 1, N) * 1.0 / 8.0;
            }
            
            cache[key] = p;
            
            return p;
        }
        
    
        int getKey(int r, int c, int remain)
        {
            return r | (c << 8) | (remain << 16);
        }
        
        
        
    private:
        unordered_map<int, double> cache;
    };
    

Log in to reply
 

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