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

桎梏普通 2023年9月17日上午9:26

class Solution {

    int m, n, k;
    boolean[][] visited;

    public int movingCount(int m, int n, int k) {
        this.m = m;
        this.n = n;
        this.k = k;
        this.visited = new boolean[m][n];
        return dfs(0, 0, 0, 0);
    }

    public int dfs(int i, int j, int si, int sj) {
        //深度优先回溯
        if (i >= m || j >= n || k < si + sj || visited[i][j]) return 0;
        visited[i][j] = true;
        return 1 + dfs(i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj) +
                   dfs(i, j + 1, si, (j + 1) % 10 !=0 ? sj + 1 : sj - 8);
    }
}

0 赞同 0 条回复

June 普通 2023年9月16日下午8:03

//未剪枝
class Solution {
    int maxn = 0;
    boolean[][] vis;
    int[][] dir = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};

    public int sumNums(int num)
    {
        int sum = 0;
        while(num > 0)
        {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }

    public int movingCount(int m, int n, int k) {
        if(m == 0)
            return 0;
        vis = new boolean[m][n];
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                vis[i][j] = false;
        dfs(0,0,m,n,k);
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
            {
                if(vis[i][j])
                    maxn++;
            }
        return maxn;
    }

    void dfs(int x,int y,int m,int n,int k)
    {
        vis[x][y] = true;

        for(int j=0;j<4;j++)
        {
            int ux = x + dir[j][0];
            int uy = y + dir[j][1];
            if(ux < 0 || ux >= m || uy >= n || uy < 0 || sumNums(ux)+sumNums(uy) > k)
                continue;
            if(vis[ux][uy])
                continue;
            dfs(ux,uy,m,n,k);
        }
    }
}

0 赞同 0 条回复

ppopp 普通 2023年9月10日上午11:02

class Solution {
public:
int res = 0;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int movingCount(int m, int n, int k) {
vector<vector> visited(m, vector(n, false));
dfs(m, n, k, 0, 0, visited);
return res;
}

void dfs(int m, int n, int k, int i, int j, vector<vector<bool>>& visited){
    if(i >= m||i < 0||j < 0||j >= n||add(i,j) > k||visited[i][j]) return;
    //做选择
    visited[i][j] = true;
    res++;

    //继续深入
    for(int p = 0; p < 4; p++){
        int x = i + dx[p];
        int y = j + dy[p];
        dfs(m, n, k, x, y, visited);
    }
}

int add(int i, int j){
    int sum = 0;
    while(i != 0){
        sum += i % 10;
        i /= 10;
    }

    while(j != 0){
        sum += j % 10;
        j /= 10;
    }

    return sum;
}

};

0 赞同 0 条回复

Marshan 普通 2023年8月23日下午11:55

效率太低了

class Solution {
public:
    // int result = 0;
    int res = 0;
    vector<vector<bool>> visited;
    int movingCount(int m, int n, int k) {
        this->visited.resize(m,vector<bool>(n,false));

        func(m,n,0,0,k);

        res = 0;
        for(const auto& row:this->visited){
            for(bool value:row){
                if(value){
                    res++;
                }
            }
        }
        return res;
    }
    void func(int m,int n,int i,int j,int k){
        if((i < 0) || (i >= m) || (j < 0) || (j >= n)){
            return;
        }
        if(visited[i][j] == true){
            return;
        }
        vector<int> temp;
        int x = i,y = j;
        while(x > 0){
            temp.push_back(x % 10);
            x /= 10;
        }
        while(y > 0){
            temp.push_back(y % 10);
            y /= 10;
        }
        int sum = 0;
        for(int num:temp){
            sum += num;
        }
        // cout<<result<<endl;
        if(sum > k){
            return;
        }

        // result++;
        // res = max(res,result);

        visited[i][j] = true;
        func(m,n,i,j+1,k);
        func(m,n,i+1,j,k);
        func(m,n,i,j-1,k);
        func(m,n,i-1,j,k);
        // visited[i][j] = false;
        // result--;
    }
};

0 赞同 0 条回复

普通 2023年8月23日下午11:09

c++代码 DFS
class Solution { //本题的思路为递归法
public:
int cal(int i,int j,int k){ //先写个计算位数和的函数cal
int sum = 0;
while(i){
sum+=i%10;
i/=10;
}
while(j)
{
sum+=j%10;
j/=10;
}
if(sum<=k)
return true;
else
return false;

}
int result = 0; 
int  a[101][101]={0}  ;
void traversal(int i, int j, int m, int n, int k){   //注意递归传入的参数有点多，顺序不要乱。result和visited必须要有&引用符号
    if(i<0||j<0||i>=m||j>=n||!cal(i,j,k) ||a[i][j]) return;      //递归终止条件，也就是走到了不符合条件的格子：1.超出边界 2.位数和大于k 3.格子已经被访问过
    a[i][j] = 1;                        //该格子符合条件，标记为true
    result++;                                    //结果+1
    traversal(i+1, j, m, n, k); //按照四个方向进行递归
    traversal(i-1, j, m, n, k);
    traversal(i, j+1, m, n, k);
    traversal(i, j-1, m, n, k);
}
int movingCount(int m, int n, int k) {
       //初始化result
    //初始化visited标记矩阵
    traversal(0, 0, m, n, k);
    return result;
}

};

0 赞同 0 条回复

人生何处不青山普通 2023年8月20日下午11:36

dfs做

function movingCount(m: number, n: number, k: number): number {
    let visited = new Array(m).fill(0).map(v => new Array(n).fill(false));
    const sum = (i: number, j: number) => i % 10 + j % 10 + Math.floor(i / 10) + Math.floor(j / 10);
    const dfs = (i: number, j: number) => {
        if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j]) return 0;
        visited[i][j] = true;
        if(sum(i,j) > k) return 0;
        return 1 + dfs(i + 1, j) + dfs(i, j + 1);
    }
    return dfs(0, 0);
};

0 赞同 0 条回复

Mby 普通 2023年8月14日下午12:43

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)
    }
}

0 赞同 0 条回复

北辰普通 2023年8月9日下午9:32

class Solution {
    public int[] dx = {-1,0,1,0};
    public int[] dy = {0,1,0,-1};
    public int movingCount(int m, int n, int k) {
        boolean[][] map = new boolean[m][n];
        int res = dfs(map,0,0,k);
        return res;
    }

    public int dfs(boolean[][] map, int x, int y, int k) {
        if(x<0||x>=map.length||y<0||y>=map[0].length||shuweihe(x)+shuweihe(y)>k||map[x][y]==true) {
            return 0;
        }
        map[x][y] = true;
        return 1+dfs(map,x+1,y,k)+dfs(map,x-1,y,k)+dfs(map,x,y-1,k)+dfs(map,x,y+1,k);
    }

    public int shuweihe(int num) {
        int sum=0;
        while(num>0) {
            sum+=num%10;
            num = num/10;
        }
        return sum;
    }

}

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

0 赞同 0 条回复

#00456B 普通 2023年8月9日上午12:20

class Solution {
public:
    int sum(int x){
        int ans = 0;
        while(x){
            ans += x%10;
            x /= 10;
        }
        return ans;
    }
    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 || i >= m || j < 0 || j >= n || visited[i][j] || sum(i) + sum(j) > k){
                return 0;
            }
            //表示访问过了
            visited[i][j] = true;
            //右 下
            return 1 + dfs(i, j + 1) + dfs(i + 1, j);
        };

        return dfs(0, 0);
    }
};

0 赞同 0 条回复

CaCO3 永久会员 2023年8月6日下午8:52

”’java
class Solution {
public int movingCount(int m, int n, int k) {
//如果一个格子不可达，那么也不能从该格子到达其他格子
//一个格子是否可达，和他周围的格子相关
if(k 0){
return 1;
}
boolean[][] vis = new boolean[m][n];
int ans = 1;
vis[0][0] = true;
for(int i = 0;i < m;i++){
for(int j = 0;j < n;j++){
if((i 0 && j 0) || sumT(i) + sumT(j) > k){
continue;
}
if(i 0){
vis[i][j] = vis[i][j-1];
}else if(j 0){
vis[i][j] = vis[i-1][j];
}else{
if(vis[i-1][j] || vis[i][j-1]){
vis[i][j] = true;
}
}

            ans += vis[i][j] ? 1:0;
        }
    }
    return ans;
}

//求一个整数的数位之和
public int sumT(int m){
    int sum = 0;
    while(m != 0){
        int res = m % 10;
        sum += res;
        m = m/10;
    }
    return sum;
}

}
”’

0 赞同 0 条回复

NullPointerException 普通 2023年8月4日下午8:31

class Solution {
boolean jude[][];
int count = 0;
int a;
int b;
public int movingCount(int m, int n, int k) {
// mn<100 从头开始上下左右
jude=new boolean[m][n];
a=m;
b=n;
backing(0,0,k);
return count;
}
public void backing(int i,int j,int k)
{
if(i<0||i>=a||j<0||j>=b||jude[i][j])
{
return;
}
if((i/10+i%10+j/10+j%10)>k)
{
return ;
}
count++;
jude[i][j]=true;//走过了永久标记
backing(i+1,j,k);
backing(i-1,j,k);
backing(i,j+1,k);
backing(i,j-1,k);

}

0 赞同 0 条回复

AD钙奶普通 2023年8月4日下午2:41

class Solution {
    int res = 0;
    public int movingCount(int m, int n, int k) {
        boolean[][] visited = new boolean[m][n];
        backTracking(0,0,m,n,k,visited);
        return res;
    }

    public void backTracking(int x, int y, int m, int n, int k,boolean[][] visited) {
        // 边界
        if(x < 0 || y < 0 || x >= m || y >= n || visited[x][y] == true) return;
        int sum = bitSum(x) + bitSum(y); 
        if(sum > k) return;
        // 逻辑
        visited[x][y] = true;
        res ++;
        // 回溯
        backTracking(x+1,y,m,n,k,visited);
        backTracking(x,y+1,m,n,k,visited);
    }
    //求数位之和
    public int bitSum (int num) {
        int sum = 0;
        while(num > 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
}

0 赞同 0 条回复

长河呼叫黄江普通 2023年8月3日上午12:08

8.2
Day24：下面是代码

class Solution {
    int m, n, k;
    boolean[][] visited;
    public int movingCount(int m, int n, int k) {
        //坐标的数位之和<=k
        this.m = m;
        this.n = n;
        this.k = k;
        this.visited = new boolean[m][n];
        return dfs(0, 0, 0, 0);
    }
    public int dfs(int i, int j, int si, int sj){
        if(i >=m || j >= n || si + sj > k || visited[i][j])
            return 0;
        visited[i][j] = true;

        return 1 + dfs(i + 1, j, (i + 1) % 10 != 0? si + 1 : si - 8, sj) 
                + dfs(i, j + 1, si, (j + 1) % 10 != 0? sj + 1 : sj - 8);
    }
}

0 赞同 0 条回复

阿尚普通 2023年8月3日上午12:01

class Solution {
    int count;
    boolean[][] record;//记录已经遍历过的点
    public int movingCount(int m, int n, int k) {
        record = new boolean[m][n];

        dfs(0, 0, m, n, k);

        return count;
    }

    public void dfs(int i, int j, int m, int n, int k){
        if(i < 0 || j < 0 || i >= m || j >= n){
            return;
        }

        if(getSum(i, j) > k || record[i][j] == true){
            return;
        }
        count += 1;
        record[i][j] = true;

        dfs(i - 1, j, m, n, k);
        dfs(i + 1, j, m, n, k);
        dfs(i, j - 1, m, n, k);
        dfs(i, j + 1, m, n, k);
    }

    private int getSum(int i, int j){
        int sum = 0;
        while(i > 0){
            sum += i % 10;
            i = i / 10;
        }
        while(j > 0){
            sum += j % 10;
            j = j / 10;
        }
        return sum;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年8月2日下午4:43

class Solution {
//    int m,n,k;
//    boolean[][] visited;
//    public int movingCount(int m, int n, int k) {
//        this.m = m;
//        this.n = n;
//        this.k = k;
//        this.visited = new boolean[m][n];
//        return dfs(0,0,0,0);
//    }
//
//    private int dfs(int i, int j, int si, int sj) {
//        if (i>=m || j>=n || (si+sj)>k || visited[i][j]) return 0;
//        visited[i][j] = true;
//        return 1 + dfs(i + 1, j, (i + 1) % 10 != 0 ? si + 1 : si - 8, sj) + dfs(i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8);
//    }

        // 这题不是回溯，这是深度优先遍历
        int m,n,k;
        boolean[][] visited;
        public int movingCount(int m, int n, int k) {
            this.m = m;
            this.n = n;
            this.k = k;
            this.visited = new boolean[m][n];
            return dfs(0,0);
        }

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

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


    }

0 赞同 0 条回复

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

共以下 15 个回答

# 回答此问题取消回复

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

共以下 15 个回答

# 回答此问题 取消回复

# 回答此问题取消回复