【回溯专题】剑指 Offer 13. 机器人的运动范围-跟着帅地玩副业，开拓第二曲线PlayOffer

陆狗陆狗普通 2024年12月23日下午11:45

解题思路
– 首先需要理解各数位之和如何计算？主要就是用当前遍历的下标i和j，比如12和13，那么数位和=1+2+1+3=7
– 遍历方向就是向右和向下（题目给的，也是可达性分析得到的结论），这种就用深度优先用递归去回溯
– 在回溯的过程中重要的一点就是要记录当前节点是否已经被遍历过，就不用进行遍历了，而且是全局唯一被遍历过即可
【题解1】

class Solution {
    // 被访问过的记录
    // 【错误点】定义boolean[]而不是定义成Boolean[]，因为默认Boolean是null会空指针，而boolean默认是false
    boolean[][] visited;
    // 棋盘大小m*n
    int m;
    int n;
    // 数位和
    int cnt;

    public int wardrobeFinishing(int m, int n, int cnt) {
        // 首先需要理解各数位之和如何计算？主要就是用当前遍历的下标i和j，比如12和13，那么数位和=1+2+1+3=7
        // 遍历方向就是向右和向下，这种就用深度优先用递归去回溯
        // 在回溯的过程中重要的一点就是要记录当前节点是否已经被遍历过，就不用进行遍历了，而且是全局唯一被遍历过即可

        // 定义数组去存储是否被遍历
        visited = new boolean[m][n];
        this.m = m;
        this.n = n;
        this.cnt = cnt;
        return dfs(0, 0);
    }

    public int dfs(int i, int j) {
        // 遍历结束的条件：边界，已经遍历过，超过数位和限制
        if (i < 0 || i >= m || j < 0 || j >= n) {
            return 0;
        }
        if (visited[i][j]) {
            return 0;
        }
        if (digit(i) + digit(j) > cnt) {
            return 0;
        }
        // 说明当前节点是可以的，进行标记
        visited[i][j] = true;
        // 继续找下面和右边的
        return 1 + dfs(i + 1, j) + dfs(i, j + 1);
    }

    // 数位的公式
    public int digit(int i) {
        int tmpt = 0;
        while (i != 0) {
            tmpt = tmpt + i % 10;
            i = i / 10;
        }
        return tmpt;
    }
}

错误点1：定义boolean[]而不是定义成Boolean[]，因为默认Boolean是null会空指针，而boolean默认是false

0 赞同 0 条回复

Xiang. 永久会员 2024年12月23日上午11:11

“`java
//思路：使用基本回溯做法即可。
class Solution {
int m;
int n;
boolean[][] visited;
public int wardrobeFinishing(int m, int n, int cnt) {
this.m=m;
this.n=n;
visited=new boolean[m][n];
return dfs(visited,0,0,cnt);
}
int dfs(boolean[][] visited,int i,int j,int cnt){
if(i>m-1||j>n-1||limit(i,j,cnt)||visited[i][j]) return 0;
visited[i][j]=true;
int res=1+dfs(visited,i,j+1,cnt)+dfs(visited,i+1,j,cnt);
return res;
}

boolean limit(int m, int n, int cnt){
    int num=0;
    while(m!=0){
        num=num+m%10;
        m/=10;
    }
    while(n!=0){
        num=num+n%10;
        n/=10;
    }
    return num>cnt;
}

}
时间复杂度：O（mn）
空间复杂度：O（mn）

0 赞同 0 条回复

秋山丽奈普通 2024年12月21日下午3:17

思路：更具题目要求，分别向下向右寻找，若不符合条件则直接返回，若符合条件递归计算

class Solution {

    boolean[][] flag;
    public int wardrobeFinishing(int row, int col, int cnt) {
        flag = new boolean[row+1][col+1];

        return clean(0, 0, row, col, cnt);
    }

    public int clean(int current_row, int current_col, int row, int col, int cnt){
        if(current_col >= col || current_row >= row){
            return 0;
        }

        if(this.flag[current_row][current_col] == true){
            return 0;
        }

        this.flag[current_row][current_col] = true;

        if(getSum(current_col) + getSum(current_row) > cnt){
            return 0;

        }else{
            System.out.println(current_row + " " + current_col);
            return 1 + clean(current_row+1, current_col, row, col, cnt) + clean(current_row, current_col+1, row, col, cnt); 

        }
    }

    public int getSum(int num){
        return num%10 + num/10;
    }
}

0 赞同 0 条回复

Kisara 普通 2024年12月18日下午8:43

回溯

class Solution {
    int count=0;
    public int wardrobeFinishing(int m, int n, int cnt) {
        boolean[][] visited=new boolean[m][n];
        return dfs(0,0,m,n,cnt,visited);
    }
    public int dfs(int i,int j,int m,int n,int cnt,boolean[][] visited){
        if(i<0||i>=m||j<0||j>=n||(i/10+i%10+j/10+j%10+i/100+j/100)>cnt||visited[i][j]) return 0;

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

0 赞同 0 条回复

苯庸普通 2024年12月18日下午3:40

class Solution {
boolean[][] visited;
public int wardrobeFinishing(int m, int n, int cnt) {
visited = new boolean[m][n];
return dfs(m, n, cnt, 0, 0);
}

int dfs(int m, int n, int cnt, int x, int y){
    if(x >= m || y >= n || getSum(x) + getSum(y) > cnt || visited[x][y]){
        return 0;
    }
    visited[x][y] = true;
    return dfs(m, n, cnt, x+1, y) + dfs(m, n, cnt, x, y+1) + 1;
}

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

}
时间：O（mn）
空间：O（mn）

0 赞同 0 条回复

Aatorx 永久会员 2024年12月18日下午3:14

class Solution {
public:
    int wardrobeFinishing(int m, int n, int cnt) {
        vector<vector<bool>> visit(m, vector<bool>(n, false));
        return recur(0, 0, cnt, visit);
    }
    int recur(int i, int j, int cnt, vector<vector<bool>>& visit) {
        int m = visit.size();
        int n = visit[0].size();
        if (i >= m || j >= n || visit[i][j] == true || digit(i) + digit(j) > cnt) {
            return 0;
        }
        visit[i][j] = true;
        int res = recur(i + 1, j, cnt, visit) + recur(i, j + 1, cnt, visit) + 1;
        return res;
    }
    int digit(int x) {
        int res = 0;
        while(x != 0) {
            res += x % 10;
            x /= 10;
        }
        return res;
    }
};

时间复杂度O(Mn)，空间复杂度O(Mn)。

0 赞同 0 条回复

月下足迹普通 2024年12月18日下午1:57

class Solution {
// 计算数字的各数位之和
private int digitSum(int x) {
int sum = 0;
while (x > 0) {
sum += x % 10;
x /= 10;
}
return sum;
}

public int wardrobeFinishing(int m, int n, int cnt) {
    // 创建一个二维数组 dp，记录每个格子是否符合整理条件
    boolean[][] dp = new boolean[m][n];

    // 初始化 dp[0][0]，只有当 digit(0) + digit(0) <= cnt 时，dp[0][0] 才是 true
    dp[0][0] = (digitSum(0) + digitSum(0) <= cnt);

    // 遍历每一行
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // 计算当前格子的数位和是否满足条件
            if (digitSum(i) + digitSum(j) <= cnt) {
                // 如果满足条件，继续判断从哪里可以到达这个格子
                if (i == 0 && j == 0) continue;  // 不需要重新计算 (0, 0)

                // 如果当前格子符合条件，并且可以从左边或者上面到达
                if (i > 0 && dp[i - 1][j]) {
                    dp[i][j] = true;
                }
                if (j > 0 && dp[i][j - 1]) {
                    dp[i][j] = true;
                }
            }
        }
    }

    // 统计需要整理的格子数量
    int result = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (dp[i][j]) result++;
        }
    }

    return result;
}

}

0 赞同 0 条回复

Jerry 普通 2024年12月17日下午10:34

class Solution {
public:
    int res = 0;
    int wardrobeFinishing(int m, int n, int cnt) {
        vector<vector<int>> valid(m, vector<int>(n, 1));
        dfs(m, n, 0, 0, cnt, valid);
        return res;
    }
    void dfs(int m, int n, int i, int j, int cnt, vector<vector<int>>& valid){
        if(i<0 || i>=m) return;
        if(j<0 || j>=n) return;
        if(valid[i][j] == 0) return;
        if(digit(i) + digit(j) > cnt) return;

        valid[i][j] = 0;
        res++;
        //cout<<"i= "<<i<<" j= "<<j<<" res= "<<res<<endl;
        dfs(m, n, i, j+1, cnt, valid);
        dfs(m, n, i+1, j, cnt, valid);
        return;
    }
    int digit(int num){
        int sum = 0;
        while(num != 0){
            sum = sum + (num%10);
            num = num/10;
        }
        return sum;
    }
};

注意点：刚开始没有考虑valid矩阵，会导致回溯时候重复计算，需注意

0 赞同 0 条回复

【回溯专题】剑指 Offer 13. 机器人的运动范围

共以下 8 个回答

# 回答此问题取消回复

【回溯专题】剑指 Offer 13. 机器人的运动范围

共以下 8 个回答

# 回答此问题 取消回复

# 回答此问题取消回复