剑指Offer 13. 机器人的运动范围

摘要：
DFS BFS模板题。

题目

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

示例 1：

输入： m = 2, n = 3, k = 1
输出： 3

示例 2：

输入： m = 3, n = 1, k = 0
输出： 1

提示：

• $1 <= n,m <= 100$
• $0 <= k <= 20$

DFS

本题是从左上向右下搜索，所以可以只用两个方向。以下代码可以进一步优化。

• C++
• Java

// 执行用时: 0 ms
// 内存消耗: 6.8 MB
class Solution {
public:

    int getTwoSum(int x, int y) {
        return getSum(x) + getSum(y);
    }

    int getSum(int x) {
        int sum = 0;
        for (; x; x /= 10) {
            sum += x % 10;
        }
        return sum;
    }

    const int dr[4] = {-1, 0, 1, 0}, dc[4] = {0, 1, 0, -1};
    int64_t res = 0;
    int g_m, g_n, g_k;
    vector<vector<bool>> st;
    int movingCount(int m, int n, int k) {
        g_m = m, g_n = n, g_k = k;
        st = vector<vector<bool>>(m, vector<bool>(n, false));
        dfs(0, 0);
        return res;
    }

    void dfs(int r, int c) {
        res++;
        st[r][c] = true;
        for (int d = 0; d < 4; d++) {
            int ner = r + dr[d], nec = c + dc[d];
            if (ner >= 0 && ner < g_m && nec >= 0 && nec < g_n && getTwoSum(ner, nec) <= g_k && !st[ner][nec]) {
                dfs(ner, nec);
            }
        }
    }
};

// 执行用时: 1 ms
// 内存消耗: 36 MB
class Solution {

    private int getSum(int x) {
        int sum = 0;
        for (; x > 0; x /= 10) {
            sum += x % 10;
        }
        return sum;
    }

    private int getTwoSum(int x, int y) {
        return getSum(x) + getSum(y);
    }

    int g_m, g_n, g_k;
    int[] dr, dc;
    boolean[][] st;
    int res = 0;
    public int movingCount(int m, int n, int k) {
        g_m = m;
        g_n = n;
        g_k = k;
        dr = new int[] {-1, 0, 1, 0};
        dc = new int[] {0, 1, 0, -1};
        st = new boolean[m][n];
        for (int i = 0; i < m; i++ ) {
            Arrays.fill(st[i], false);
        }

        dfs(0, 0);

        return res;
    }

    private void dfs(int r, int c) {
        res++;
        st[r][c] = true;
        for (int d = 0; d < 4; d++) {
            int ner = r + dr[d], nec = c + dc[d];
            if (ner >= 0 && ner < g_m && nec >= 0 && nec < g_n && !st[ner][nec] && getTwoSum(ner, nec) <= g_k) {
                dfs(ner, nec);
            }
        }
    }
}

BFS

注意响铃节点的竞争问题，要在下一个节点入队时将节点更新成已占据，以避免此问题。

• c++
• java

// 执行用时: 4 ms
// 内存消耗: 6.4 MB
class Solution {
public:
    
    int getSum(int x) {
        int sum = 0;
        for (; x; x /= 10) {
            sum += x % 10;
        }
        return sum;
    }

    int getTwoSum(int x, int y) {
        return getSum(x) + getSum(y);
    }


    int g_m, g_n, g_k;
    vector<vector<bool>> st;
    const int dr[4] = {0, 1}, dc[4] = {1, 0};
    int res = 0;
    int movingCount(int m, int n, int k) {
        g_m = m, g_n = n, g_k = k;
        st = vector<vector<bool>>(m, vector<bool>(n, false));

        bfs({0, 0});

        return res;
    }

    void bfs(pair<int, int>) {
        queue<pair<int, int>> q;
        q.push({0, 0});
        st[0][0] = true;

        for (; q.size();) {
            int r = q.front().first, c = q.front().second;
            q.pop();
            res++;
            for (int d = 0; d < 2; d++) {
                int ner = r + dr[d], nec = c + dc[d];
                if (ner >= 0 && ner < g_m && nec >= 0 && nec < g_n && !st[ner][nec] && getTwoSum(ner, nec) <= g_k) {
                    q.push({ner, nec});
                    st[ner][nec] = true;    // 避免相邻节点竞争
                }
            }
        }
    }
};

// 执行用时: 5 ms
// 内存消耗: 35.8 MB
class Solution {
    int getSum(int x) {
        int sum = 0;
        for (; x > 0; x /= 10) {
            sum += x % 10;
        }
        return sum;
    }

    int getTwoSum(int x, int y) {
        return getSum(x) + getSum(y);
    }

    int m, n, k;
    int[] dr, dc;
    boolean[][] st;
    int res = 0;
    public int movingCount(int m, int n, int k) {
        this.m = m;
        this.n = n;
        this.k = k;
        dr = new int[] {0, 1};
        dc = new int[] {1, 0};
        st = new boolean[m][n];
        for (int i = 0; i < m; i ++) {
            Arrays.fill(st[i], false);
        }

        bfs(0 * n + 0);

        return res;
    }

    private void bfs(int hash) {
        Queue<Integer> q = new LinkedList<>();
        q.add(hash);
        st[0][0] = true;

        for (; q.size() > 0;) {
            int _hash = q.remove();
            int r = _hash / n, c = _hash % n;
            res++;

            for (int i = 0; i < 2; i++) {
                int ner = r + dr[i], nec = c + dc[i];
                if (ner >= 0 && ner < m && nec >= 0 && nec < n && !st[ner][nec] && getTwoSum(ner, nec) <= k) {
                    q.add(ner * n + nec);
                    st[ner][nec] = true;
                }
            }
        }
    }
}

原题链接： 剑指Offer 13. 机器人的运动范围