本问题对应的 leetcode 原文链接：剑指 Offer 13. 机器人的运动范围

问题描述

地上有一个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

解题思路

视频讲解直达： 本题视频讲解

代码实现

class Solution {
    int m;
    int n;
    int k;
    boolean[][] visited;
    public int movingCount(int m, int n, int k) {
        this.m = m;
        this.n = n;
        this.k = k;
        visited = new boolean[m][n];

        return dfs(0, 0);
    }

    int dfs(int i, int j){
        // 是否在方格之内或者是否访问过或者是否是障碍物
        if(i < 0 || j < 0 || i >= m || j >= n || visited[i][j] || k < sum(i) + sum(j)){
            return 0;
        }

        visited[i][j] = true;
        return 1 + dfs(i + 1, j) + dfs(i, j + 1);
    }

    int sum(int x){
        int res = 0;
        while(x != 0){
            res = res + x % 10;
            x = x / 10;
        }
        return res;
    }
}

时间复杂度：O(mn)
空间复杂度：O(mn)

Python

class Solution(object):
    def movingCount(self, m, n, k):
        """
        :type m: int
        :type n: int
        :type k: int
        :rtype: int
        """
        visited = [[False] * n for _ in range(m)]

        def dfs(i, j):
            if i < 0 or j < 0 or i >= m or j >= n or visited[i][j] or k < self.sum(i) + self.sum(j):
                return 0

            visited[i][j] = True
            return 1 + dfs(i + 1, j) + dfs(i, j + 1)

        return dfs(0, 0)

    def sum(self, x):
        res = 0
        while x != 0:
            res += x % 10
            x //= 10
        return res

C++

class Solution {
public:
    int movingCount(int m, int n, int k) {
        vector<vector<bool>> visited(m, vector<bool>(n, false));

        function<int(int, int)> dfs = [&](int i, int j) -> int {
            if (i < 0 || j < 0 || i >= m || j >= n || visited[i][j] ||
                k < sum(i) + sum(j)) {
                return 0;
            }

            visited[i][j] = true;
            return 1 + dfs(i + 1, j) + dfs(i, j + 1);
        };

        return dfs(0, 0);
    }

private:
    int sum(int x) {
        int res = 0;
        while (x != 0) {
            res += x % 10;
            x /= 10;
        }
        return res;
    }
};

Go

func movingCount(m int, n int, k int) int {
    visited := make([][]bool, m)
    for i := range visited {
        visited[i] = make([]bool, n)
    }

    var dfs func(int, int) int
    dfs = func(i, j int) int {
        if i < 0 || j < 0 || i >= m || j >= n || visited[i][j] ||
            k < sum(i)+sum(j) {
            return 0
        }

        visited[i][j] = true
        return 1 + dfs(i+1, j) + dfs(i, j+1)
    }

    return dfs(0, 0)
}

func sum(x int) int {
    res := 0
    for x != 0 {
        res += x % 10
        x /= 10
    }
    return res
}

JS

/**
 * @param {number} m
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var movingCount = function(m, n, k) {
    // 初始化变量
    let visited = new Array(m).fill().map(() => new Array(n).fill(false));

    // 开始搜索
    return dfs(0, 0);

    function dfs(i, j) {
        // 是否在方格之内或者是否访问过或者是否是障碍物
        if(i < 0 || j < 0 || i >= m || j >= n || visited[i][j] || k < sum(i) + sum(j)){
            return 0;
        }

        visited[i][j] = true;
        return 1 + dfs(i + 1, j) + dfs(i, j + 1);
    }

    function sum(x) {
        let res = 0;
        while(x !== 0){
            res = res + x % 10;
            x = Math.floor(x / 10);
        }
        return res;
    }
};

shuaidi永久会员

收藏 海报挣佣金 推广链接