ARST打卡第119周[119/521]

发表于 2021-08-15 分类于 ARST 阅读次数：

lc576_出界的路径数【TED演讲】不要为难民难过，请相信他们 python日志最佳实践字符拼接数字[最佳实践] snprintf返回值判断-返回值深入实践分析

Algorithm

lc576_出界的路径数

思路

直接bfs遍历搜索max_count步，然后有出界就+1

但是到达边界之后，它可以出界也可以绕圈，所以到达边界时有很多种

max_count = 1,那么只有直接出界(add_count = 靠近的边界数)，1，2，3，4都有可能
max_count = 2, 包含max_count = 1的情况，也有走其他方向后继续递归到max_count = 1的情况

2021年08月15日12:41:16 搞了一个小时，然后76 / 94 个通过测试用例, 第76个用例超时了，自己菜了好多，看题解吧

代码

超时代码分析

因为可以走回头路的原因
朴素的层序宽搜每一层引入的路径节点的数量会随着深度呈指数数级扩张，导致最后遍历不动

class Solution {
public:
    typedef struct pos_count {
        int m_x;
        int m_y;
        int m_rem_count;
        pos_count(int x, int y, int rem_count) : m_x(x), m_y(y), m_rem_count(rem_count) {}
    } pos_count_t;

    /* 计算出靠近几个边界 
     */
    int edgeCount(int m, int n, int x, int y) {
        int tmp = 0;
        tmp += x == 0 ? 1 : 0; 
        tmp += x == m - 1 ? 1 : 0; 
        tmp += y == 0 ? 1 : 0; 
        tmp += y == n - 1 ? 1 : 0;
        return tmp; 
    }

    int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        if (maxMove <= 0) {
            return 0;
        }

        if (m == 1 && n == 1) {
            return 4; // 直接4个方向一次出去
        }
        
        queue<pos_count_t> Q;
        long long ans = 0;
        long long mod = 1e9 + 7;
        int xf[] = {0, 0, 1, -1};
        int yf[] = {1, -1, 0, 0};
        int fi, se, remMove;
        Q.push({startRow, startColumn, maxMove});
        while (!Q.empty()) {
            pos_count_t tmp = Q.front();
            Q.pop();
            fi = tmp.m_x;
            se = tmp.m_y;
            remMove = tmp.m_rem_count - 1;
            ans = (ans + edgeCount(m, n, fi, se)) % mod;

            if (remMove == 0) {
                continue;
            }
            for (int i = 0; i < 4; i++) {
                int x = fi + xf[i];
                int y = se + yf[i];
                if (x < 0 || x > m - 1 || y < 0 || y > n - 1) {
                    continue;
                }
                Q.push({x, y, remMove});
            }
        }

        return ans;
    }
};

正确dp姿势

题解

class Solution {
public:
    static constexpr int MOD = 1'000'000'007;

    int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        vector<vector<int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int outCounts = 0;
        vector<vector<vector<int>>> dp(maxMove + 1, vector<vector<int>>(m, vector<int>(n)));
        dp[0][startRow][startColumn] = 1;
        for (int i = 0; i < maxMove; i++) {
            for (int j = 0; j < m; j++) {
                for (int k = 0; k < n; k++) {
                    int count = dp[i][j][k];
                    if (count > 0) {
                        for (auto &direction : directions) {
                            int j1 = j + direction[0], k1 = k + direction[1];
                            if (j1 >= 0 && j1 < m && k1 >= 0 && k1 < n) {
                                dp[i + 1][j1][k1] = (dp[i + 1][j1][k1] + count) % MOD;
                            } else {
                                outCounts = (outCounts + count) % MOD;
                            }
                        }
                    }
                }
            }
        }
        return outCounts;
    }
};