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

Gg 普通 2023年8月1日下午11:46

class Solution {
    private int k;
    private int m;
    private int n;
    private boolean[][] visited;

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

    public int dfs(int i, int j, int iSplitSum, int jSplitSum){
        // 不满足直接返回0
        if(i >= m || j >= n 
        || visited[i][j] || iSplitSum + jSplitSum > k){
            return 0;
        }
        // 记录已经检查过的
        this.visited[i][j] = true;
        // 检查右或下一个
        return 1 
        + dfs(i+1,j,(i+1)% 10 != 0 ? iSplitSum + 1: iSplitSum - 8,jSplitSum) 
        + dfs(i,j+1,iSplitSum, (j+1) % 10 != 0 ? jSplitSum + 1: jSplitSum -8);
    }
}

0 赞同 0 条回复

宁永久会员 2023年3月17日下午7:59

class Solution {
    boolean[][] arr;
    public int movingCount(int m, int n, int k) {
        arr = new boolean[m][n];
        return backTracing(0, 0, k); 
    }
    int backTracing(int i, int j, int k){
        if(i < 0|| i >= arr.length || j < 0|| j >= arr[0].length ||sum(i) + sum(j) > k || arr[i][j]) return 0;
        arr[i][j] = true;
        //访问过的标记为TRUE之后就不会重复访问了
        //优化：向下和向右搜索已经可以访问到所有可达元素了
        return 1 + backTracing(i + 1, j, k) + backTracing(i, j + 1, k);
    }
    int sum (int i){
        int sum = 0;
        while(i != 0){
            sum += i % 10;
            i /= 10;
        }
        return sum;
    }
}

0 赞同 0 条回复

PatNick 普通 2023年1月17日下午7:28

class Solution:
    def __init__(self):
        # 这里用set存放标记
        self.invisitedList = set()
        self.m = 0
        self.n = 0
        self.k = 0

    def movingCount(self, m, n, k):
        self.m = m
        self.n = n
        # self.invisitedList = [[False for _ in range(n)] for __ in range(m)]
        self.k = k

        res = self.dsf(0,0)

        return res




    def dsf(self,i,j):
        # 越界，已标记，大于k
        if i < 0 or i >= self.m or j < 0 or j >= self.n or (i,j) in self.invisitedList or self.sum(i,j) > self.k:
            return 0

        self.invisitedList.add((i,j))

        return 1 + self.dsf(i,j+1) + self.dsf(i+1,j) + self.dsf(i,j-1) + self.dsf(i-1,j)




    def sum(self,x,y):
        if x // 10:
            sum1 = x // 10 + x % 10
        else:
            sum1 = x
        if y // 10:
            sum2 = y // 10 + y % 10
        else:
            sum2 = y
        return sum2 + sum1

0 赞同 0 条回复

lucca 普通 2023年1月16日下午6:27

BFS

时间复杂度 O(NM)
空间复杂度 O(NM)

class Solution {
    public int movingCount(int n, int m, int k) {
        if (k == 0) return 1;

        int[] r = new int[n], c = new int[m];
        for (int i = 0; i < n; i++) {
            int t = i;
            while (t > 0) {
                r[i] += t % 10;
                t /= 10;
            }
        }
        for (int i = 0; i < m; i++) {
            int t = i;
            while (t > 0) {
                c[i] += t % 10;
                t /= 10;
            }
        }

        int[] dx = {0, 1}, dy = {1, 0};
        boolean[][] vis = new boolean[n][m];
        Queue<int[]> q = new LinkedList<>();

        int sum = 1;
        q.add(new int[]{0, 0});
        vis[0][0] = true;

        while (!q.isEmpty()) {
            int[] p = q.poll();
            for (int i = 0; i < 2; i++) {
                int x = p[0] + dx[i], y = p[1] + dy[i];
                if (x >= 0 && x < n && y >= 0 && y < m && !vis[x][y] && r[x] + c[y] <= k) {
                    vis[x][y] = true;
                    q.add(new int[]{x, y});
                    sum++;
                }
            }
        }
        return sum;
    }
}

0 赞同 0 条回复

@ 普通 2022年12月13日下午9:20

时间复杂度：O(MN)

空间复杂度：O(MN)

class Solution {
    private int row;
    private int col;

    private boolean[][] vist; //用来记录已拜访过的格子

    public int movingCount(int m, int n, int k) {
        this.row = m;
        this.col = n;

        this.vist = new boolean[m][n];

        int res = dfs(0, 0, k);

        return res;

    }

    public int dfs(int i, int j, int k) {
        if (i < 0 || i > row || j < 0 || j > col || vist[i][j])
            return 0;

        vist[i][j] = true;

        List<Integer> list1 = split(i);
        List<Integer> list2 = split(j);
        Integer sum = list1.stream().reduce(0, Integer::sum) + list2.stream().reduce(0, Integer::sum);
       //行坐标和列坐标的数位之和大于k的格子则不符合
        if (sum > k)
            return 0;


        int right = dfs(i, j + 1, k);
        int bottom = dfs(i + 1, j, k);
        int left = dfs(i, j - 1, k);
        int top = dfs(i + 1, j, k);

        return 1 + right + left + top + bottom;


    }


    //拆分，比如传入 37 ， 返回的list集合则含有 3 7
    List<Integer> split(int num) {
        List<Integer> result = new ArrayList<>();

        int count = 0;
        while (true) {
            result.add(num % 10);
            num /= 10;
            if (num == 0) break;
        }

        return result;
    }

}

0 赞同 0 条回复

symbol 普通 2022年12月3日上午7:49

//深度优先遍历
var n1, m1, k1 int
var visited [][]bool

func movingCount(m int, n int, k int) int {
    m1 = m
    n1 = n
    k1 = k
    visited = make([][]bool, m)
    for i := 0; i < len(visited); i++ {
        visited[i] = make([]bool, n)
    }

    return dfs(0, 0, 0, 0)
}

func dfs(i int, j int, si int, sj int) int {
    if i >= m1 || j >= n1 || si+sj > k1 || visited[i][j] {
        return 0
    }
    visited[i][j] = true

    sj1 := sj + 1
    si1 := si + 1
    if (j+1)%10 == 0 {
        sj1 = sj - 8
    }
    if (i+1)%10 == 0 {
        si1 = si - 8
    }

    return 1 + dfs(i, j+1, si, sj1) + dfs(i+1, j, si1, sj)
}

0 赞同 0 条回复

你有点可爱喔普通 2022年12月2日下午4:43

class Solution {
    public int movingCount(int m, int n, int k) {
            //左、右、上、下移动一格（不能移动到方格外）;行坐标和列坐标的数位之和大于k
            boolean [][]visited = new boolean[m][n];
            return dfs(0,0,m,n,k,visited);
    }
    private int dfs(int i,int j,int m,int n,int k,boolean visited[][]){
        if (i < 0 || i >= m || j < 0 || j >= n || (i/10 + i%10 + j/10 + j%10) > k || visited[i][j]) {
            return 0;
        }
        visited[i][j] = true;
        return dfs(i + 1, j, m, n, k, visited) + dfs(i - 1, j, m, n, k, visited) + 
               dfs(i, j + 1, m, n, k, visited) + dfs(i, j - 1, m, n, k, visited) + 1;
    }
}

0 赞同 0 条回复

T 普通 2022年11月30日上午9:37

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 backtrace(0, 0, k);
    }

    private int backtrace(int i, int j, int k) {
        //如果当前格子超过边界或者大于k值或者已被访问就返回
        if(i >= m || j >= n || (sum(i) + sum(j)) > k || visited[i][j]) return 0;
        visited[i][j] = true;
        return 1 + backtrace(i + 1, j, k) + backtrace(i, j + 1, k);
    }

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

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月23日下午4:51

时间空间复杂度都为O（mn）

class Solution {
    boolean[][] visited;
    int k1;
    int m1;
    int n1;
    public int movingCount(int m, int n, int k) {
        visited = new boolean[m][n];
        k1 = k;
        m1 = m;
        n1 = n;
        return dfs(0,0);
    }
    int dfs(int i,int j){
        if(i < 0 || i >= m1 || j < 0 || j >= n1 || visited[i][j] || sum(i) + sum(j) > k1) return 0;
        visited[i][j] = true;
        int a =  dfs(i + 1,j);
        int b =  dfs(i,j + 1);
        //每递归成功一次就加1
        return a + b + 1;
    }
    int sum(int sum){
        int res = 0;
        while(sum != 0){
            res += sum % 10;
            sum = sum/10;
        }
        return res;
    }
}

0 赞同 0 条回复

庄重普通 2022年11月23日下午3:58

// 思路：
//     1.机器人进行向右向下的深度搜索,搜索过的进行标识即可
class Solution {
public:
    int movingCount(int m, int n, int k) {
        this->m = m;
        this->n = n;
        this->k = k;
        visited = vector<vector<bool>>(m, vector<bool>(n, false));

        return dfs(0,0);
    }

private:
    int dfs(int i, int j){
        //越界或者被重复访问或不满足条件返回0
        if(i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || sum(i) + sum(j) > k){
            return 0;
        }
        visited[i][j] = true;
        //优化：由于机器人不可访问的坐标具有一定的规律性，深度搜索只需要进行向下向右搜索即可
        //否则还是进行4个方向的深度搜索
        //这个位置需要加1，否则最后只会返回0
        return 1 + dfs(i+1, j) + dfs(i, j+1);
    }
    int sum(int x){
        int ret = 0;
        while(x != 0){
            ret += x % 10;
            x /= 10;
        }
        return ret;
    }

    int m;
    int n;
    int k;
    vector<vector<bool>> visited;
};
//时间复杂度O(nm) nm为方格的行列
//空间复杂度O(mn)

0 赞同 0 条回复

訁訁訁訁訁普通 2022年11月21日下午11:17

dfs

时间复杂度O(mn)

空间复杂度O(mn)

class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.movingCount(2, 3, 1));
    }
    boolean[][] visited;
    int count = 0;
    public int movingCount(int m, int n, int k) {
        visited =  new boolean[m][n];
        dfs(m,n,0,0,k);
        return count;
    }
    public void dfs(int m,int n,int i,int j,int k ){
        if(i < 0 || i >= m || j < 0 || j >= n ||visited[i][j] ||(i%10+i/10+j%10+j/10) > k){
            return ;
        }
        count++;
        visited[i][j] = true;
        dfs(m,n,i+1,j,k);
        dfs(m,n,i-1,j,k);
        dfs(m,n,i,j-1,k);
        dfs(m,n,i,j+1,k);
    }

}

0 赞同 0 条回复

Tolkien 永久会员 2022年11月21日下午10:44

public class Solution {
    private boolean[][] visited;
    private int m, n;
    private int k;
    /**
     * dfs
     * 时间复杂度：O(mn)
     * 空间复杂度：O(mn)
     */
    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);
    }

    private int dfs(int i, int j) {
        // 1. 剪枝
        // 数组出界 或 所在点位超过k 或 访问过
        if (i > m-1 || i < 0 || j > n-1 || j < 0 || getSum(i)+getSum(j) > k || visited[i][j]) {
            return 0;
        }

        // 2. 选择此阶段其中一个解，将其加入到已选解集合中
        visited[i][j] = true;

        // 3. 进入下一阶段
        return 1+dfs(i+1, j)+dfs(i, j+1)+dfs(i-1, j)+dfs(i, j-1);
    }

    private int getSum(int val) {
        int result = 0;

        while (val != 0) {
            result += val % 10;
            val /= 10;
        }

        return result;
    }
}

0 赞同 0 条回复

So 普通 2022年11月21日下午7: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 || i >= m || j < 0 || 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 += x % 10;
            x /= 10;
        }
        return res;
    }
}

时间：O(mn)，空间：O(mn)

0 赞同 0 条回复

青木普通 2022年11月20日下午11:44

/** 
    人麻了，写的注释没保存上
    就是将问题变成了只用向下和向右，并抽象为找点问题，用visited记录已访问的点

    时间O(m*n)
    空间O(m*n)
 */


class Solution {
    boolean[][] visited;
    int m,n,k;
    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 || si + sj > k || visited[i][j]) return 0;
        visited[i][j] = true;
        return 1 + dfs(i+1, j, count(i+1), sj) + dfs(i, j+1, si, count(j+1));
        // 高级写法
        // 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);
    }

    public int count(int a){
        int res = 0;
        while(a > 0){
            res += a%10;
            a = a/10;
        }
        return res;
    }
}


/**
    受题解启发，把之前错误的实现纠正了一下，
    就是没反应过来visit不用再恢复原来状态，属于是阅读理解有问题了T_T
 */

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 backtrack(0, 0);
    }

    public int backtrack(int i, int j){
        if(i<0 || j>=n || i>=m || j<0 || count(i,j)>k || visited[i][j]){
            return 0;
        }
        visited[i][j] = true;
        int res = 1 + backtrack(i+1, j) + backtrack(i-1, j) +
                    backtrack(i, j+1) + backtrack(i,j-1);
        return res;
    }


    public int count(int a, int b){
        int res = 0;
        while(a > 0){
            res += a%10;
            a = a/10;
        }
        while(b > 0){
            res += b%10;
            b = b/10;
        }
        return res;
    }
}

0 赞同 0 条回复

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

共以下 14 个回答

BFS

# 回答此问题取消回复

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

共以下 14 个回答

BFS

# 回答此问题 取消回复

# 回答此问题取消回复