题目来源：https://www.acwing.com/problem/content/22/

题目描述

具体代码

解题思路： 题目中有限制机器人移动的参数，此时每个方格都可以有三种状态（机器人不可以走的方格、机器人可以走但还没走过的方格、机器人已经走过的方格），对于这三种状态我们分别使用-1
、0
、1
来表示。最后只需要查看有多少个状态为1
的方格即可得出答案。

class Solution {
    // 每个方格的状态表
    public int[][] table;
    // 总行数
    public int rows;
    // 总列数
    public int cols;
    
    public int movingCount(int threshold, int rows, int cols) {
    	// 初始化基本数据
        table = new int[rows][cols];
        this.rows = rows;
        this.cols = cols;
        // 找出机器人不能够走的方格，并将状态标为-1
        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < cols; j++) {
                String string = String.valueOf(i) + String.valueOf(j);
                int sum = 0;
                for(char c : string.toCharArray()) {
                    sum += Integer.valueOf(String.valueOf(c));
                    if(sum > threshold) {
                        table[i][j] = -1;
                    }
                }
            }
        }
        // 深度搜索
        dfs(0, 0);
        
        int count = 0;
        
        // 找出所有标记为1的方格，即为答案
        for(int i = 0; i < rows; i++) {
            for(int j = 0; j < cols; j++) {
                if(table[i][j] == 1) {
                    count++;
                }
            }
        }
        return count;
    }
    
    public void dfs(int x, int y) {
    	// 遍历到超出范围、状态为1或-1的方格时停止此次的dfs
        if(x < 0 || y < 0 || x > cols-1 || y > rows-1 || table[y][x] != 0) {
            return;
        }
        // 将当前的方格标记为1
        table[y][x] = 1;
        // 分别对应机器人上、下、左、右移动的情况
        dfs(x, y-1);
        dfs(x, y+1);
        dfs(x-1, y);
        dfs(x+1, y);
    }
}

运行结果

输入：

18
40
40

输出：

1484

若上述代码存在任何问题，或者您有更优解，欢迎在下方评论区提出~！