# C++; top-down; symmetry exploitation

• 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;
}
};

``````

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