688. Knight Probability in Chessboard

dp O(N²K) time O(N²) space
千万不要理解成bfs！！！每走一步需要记录整个棋盘的状态，所以是dp

class Solution {
public:
    double knightProbability(int N, int K, int r, int c) {
        vector<vector<double>> f(N, vector<double>(N));
        f[r][c] = 1;
        int dr[] = {-2, -1, 1, 2, 2, 1, -1, -2}, dc[] = {1, 2, 2, 1, -1, -2, -2 ,-1};
        while (K-- > 0) { // 每走一步，重绘棋盘
            vector<vector<double>> t(N, vector<double>(N));
            for (int r = 0; r < N; ++r) {
                for (int c = 0; c < N; ++c) {
                    if (f[r][c] < 1e-8) continue; // 浮点数，不要直接跟0比
                    for (int i = 0; i < 8; ++i) {
                        int rr = r + dr[i], cc= c + dc[i];
                        if (rr < 0 || rr >= N || cc < 0 || cc >= N) continue;
                        t[rr][cc] += f[r][c] * 0.125; // 累加当前位置出现queen的概率
                    }
                }
            }
            t.swap(f);
        }
        double res = 0;
        for (int r = 0; r < N; ++r) {
            for (int c = 0; c < N; ++c) {
                res += f[r][c]; // 累加当前棋盘所有位置queen出现的概率和
            }
        }
        return res;
    }
};