九号球普通 2023年11月30日下午10:08

“`java
class Solution {
public int wardrobeFinishing(int m, int n, int cnt) {
if (cnt == 0) {
return 1;
}
Queue queue = new LinkedList<>();
//向右和向下的数组
int[] dx = {0, 1};
int[] dy = {1, 0};
boolean[][] vis = new boolean[m][n];
queue.offer(new int[]{0, 0});
int ans = 1;
vis[0][0] = true;
while (!queue.isEmpty()) {
int[] arr = queue.poll();
for (int i = 0; i < 2; i++) { int x = dx[i] + arr[0]; int y = dy[i] + arr[1]; if (x < 0 || x >= m || y < 0 || y >= n || vis[x][y] || get(x) + get(y) > cnt) {
continue;
}
queue.offer(new int[]{x, y});
vis[x][y] = true;
ans++;
}
}
return ans;
}

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

}

0 赞同 0 条回复

招舟子普通 2023年9月9日上午10:40

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;
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]true||k<(sum(i)+sum(j))){
return 0;
}
visited[i][j]=true;
int tmp = 1+dfs(i,j+1)+dfs(i+1,j)+dfs(i,j-1)+dfs(i-1,j);
return tmp;

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

}
递归

0 赞同 0 条回复

桀桀桀Jay 普通 2023年8月4日下午1:25

java
class Solution {
    public static int count = 0;
    public int movingCount(int m, int n, int k) {
        //定义数组来存放该元素是否已被访问
        boolean[][] visited = new boolean[m][n]; 

        return dfs(0, 0, m, n, k, visited);
        //return count; 
    }

    public int dfs(int i, int j, int m, int n, int k, boolean[][] visited) {
        //不满足判断条件剪枝，在边界外时，数位之和大于时, 节点已经访问过时
        if(i >= m || j >= n || visited[i][j] || bitSumGreater(i, j, k)) {
            return 0;
        }

        count++;  //将第一次访问到的该节点计数
        visited[i][j] = true; //表示已经访问过了该节点

        //只需要往下往右就能探索到所有可访问的节点
        //dfs(i+1, j, m, n, k, visited);
        //dfs(i, j+1, m, n, k, visited);

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

    public boolean bitSumGreater(int i, int j, int k) {
        int sum = 0;
        while(i != 0) {
            sum += i % 10;
            i /= 10;
        }
        while(j != 0) {
            sum += j % 10;
            j /= 10;
        }

        if(sum > k) {
            return true;
        }
        return false;
    }
}

时间复杂度O(MN), 空间复杂度O(N+M)

0 赞同 0 条回复

张开怀普通 2023年7月24日上午11:25

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

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

0 赞同 0 条回复

BOZ 普通 2023年7月20日上午11:13

【思路】用深度优先遍历
【复杂度】时间复杂度O(mn)，空间复杂度O(mn)

class Solution {
    char **mark;
    int m, n, k;

    void dfs(int i, int j) {
        if (i < 0 || i >= m || j < 0 || j >= n || !(mark[i][j] & 1) || (mark[i][j] & 2)) return;
        mark[i][j] |= 2;        // mark visited

        // visit neighbors
        dfs(i + 1, j);
        dfs(i, j + 1);
    }

    bool confirm(int i, int j) {
        int sum = 0;
        while(i) {sum += i % 10; i /= 10;}
        while(j) {sum += j % 10; j /= 10;}
        return (sum <= k);
    }

public:
    int movingCount(int m, int n, int k) {
        this->m = m;
        this->n = n;
        this->k = k;

        // initialize mark matrix && to_visit set
        mark = new char*[m];
        for (int i = 0; i < m; i++) {
            mark[i] = new char[n];
            for (int j = 0; j < n; j++) mark[i][j] = confirm(i, j);
        }

        dfs(0, 0);

        int sum = 0;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                sum += (mark[i][j] & 2) >> 1;
        return sum;
    }
};

0 赞同 0 条回复

怀瑾永久会员 2023年7月20日上午8:30

C++实现

“`C++
int digitSum(int num) {
int sum = 0;
while (num > 0) {
sum += num % 10;
num /= 10;
}
return sum;
}

int dfs(std::vector<std::vector>& visited, int row, int col, int m, int n, int k) {
if (row < 0 || row >= m || col < 0 || col >= n || visited[row][col] || digitSum(row) + digitSum(col) > k) {
return 0;
}

visited[row][col] = true;
int count = 1;

count += dfs(visited, row - 1, col, m, n, k);
count += dfs(visited, row + 1, col, m, n, k);
count += dfs(visited, row, col - 1, m, n, k);
count += dfs(visited, row, col + 1, m, n, k);

return count;

}

int movingCount(int m, int n, int k) {
std::vector<std::vector> visited(m, std::vector(n, false));
return dfs(visited, 0, 0, m, n, k);
}

“`

0 赞同 0 条回复

yxy 普通 2023年7月17日上午11:43

复杂度O(mn)

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
class Solution {
    bool satify(int x, int y, int k)
    {
        int res=0;
        while(x)
        {
            res+=x%10;
            x/=10;
        }
        while(y)
        {
            res+=y%10;
            y/=10;
        }
        return res<=k;
    }
    void dfs(vector<vector<int>>& v, int x, int y, int k, int m, int n)
    {
        res++;
        if(x==m-1&&y==n-1) return;
        for(int i=0;i<4;i++)
        {
            int a=x+dx[i];
            int b=y+dy[i];
            // cout<<a<<" "<<b<<" "<<satify(a,b,k)<<endl;
            if(a>=0&&a<m && b>=0&&b<n && v[a][b]==1 && satify(a,b,k))
            {
                // cout<<a<<" "<<b<<endl;
                v[a][b]=0;
                dfs(v, a, b, k, m, n);
            }
        }
    }
    int res;
public:
    int movingCount(int m, int n, int k) {
        res = 0;
        vector<vector<int>> v(m, vector<int>(n, 1));
        v[0][0]=0;
        dfs(v, 0, 0, k, m, n);
        return res;
    }
};

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年7月17日上午6:16

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:

        visited = [[0] * n for _ in range(m)]

        def digitSum(num):
            digitS = 0
            while num > 0:
                digitS += num % 10
                num //= 10

            return digitS

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

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

        return dfs(0, 0)

右下

0 赞同 0 条回复

Vow the vow。普通 2023年7月16日下午12:19

向右向下。

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

    private void dfs(int i, int j, int k){
        if(i < 0 || i >= m || j < 0 || j >= n) return;
        if(visited[i][j]) return;
        if(sum(i,j) > k) return;
        res++;
        visited[i][j] = true;
        for(int[] d : directions){
            dfs(i+d[0],j+d[1],k);
        }
        // visited[i][j] = false;
    }

    private int sum(int x, int y){
        int count = 0;
        while(x > 0){
            count += x % 10;
            x /= 10;
        }
        while(y > 0){
            count += y % 10;
            y /= 10;
        }
        return count;
    }

0 赞同 0 条回复

Dsjh 普通 2023年7月16日上午11:59

MY

广度遍历，
可以只向下，向右遍历

class Solution {
public:
    vector<int> dir{-1,0,1,0,-1};
    vector<vector<char>> board;
    int movingCount(int m, int n, int k) {
        int ans=0;
        board = vector<vector<char>>(m,vector<char>(n,'#'));
        board[0][0] = ',';
        deque<pair<int,int>> q;
        q.push_back(make_pair(0,0));
        while(!q.empty()){
            int size = q.size();
            ans += size;
            while(size--){
                int i=q.front().first,j=q.front().second;

                q.pop_front();
                for(int t=0;t<4;t++){
                    int x=i+dir[t],y=j+dir[t+1];
                    if(x>=0 && x<m && y>=0 && y<n && func(x,y,k)){
                        q.push_back(make_pair(x,y));
                    }
                }
            }
        }
        return ans;
    }
    bool func(int x,int y,int k){
        if(board[x][y] == ',')
            return false;
        int temp = 0;
        int i=x,j=y;
        while(x/10 != 0){
            temp += x%10;
            x /= 10;
        }
        temp += x;
        while(y/10 != 0){
            temp += y%10;
            y /= 10;
        }

        temp += y;
        if(temp > k){
            return false;
        }
        else{
            board[i][j] = ',';
            return true;
        }
    }

};

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月16日上午12:08

class Solution {
    public int count = 0;
    public int m;
    public int n;
    public boolean[][] visited;

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

    void dfs(int m,int n,int k){
        //判断边界
        if(m < 0 || m >= this.m){
            return;
        }
        if(n < 0 || n >= this.n){
            return;
        }
        //判断是否访问过
        if(visited[m][n]){
            return;
        }
        //判断是否满足
        if(!check(m,n,k)){
            return;
        }

        //此时，表示当前位置可以访问
        count++;
        visited[m][n] = true;
        dfs(m - 1,n,k);
        dfs(m + 1,n,k);
        dfs(m,n + 1,k);
        dfs(m,n - 1,k);

        //回溯到此，重置标志位
        //visited[m][n] = false;
        //此题不用重置标志位！！访问过就是访问过，与上一题不一样

    }

    boolean check(int m,int n,int k){
        int sum = 0;
        while(m != 0){
            sum = sum + (m % 10);
            m = m / 10;
        }
        while(n != 0){
            sum = sum + (n % 10);
            n = n / 10;
        }
        if(sum > k){
            return false;
        }

        return true;
    }

}

0 赞同 0 条回复

Yodl. 普通 2023年7月15日下午9:30

//时间复杂度：O(mn) 空间复杂度：O(mn)
class Solution {
public:
    int movingCount(int m, int n, int k) {
        vector<vector<bool>> visited(m, vector<bool>(n, 0));
        return dfs(0, 0, 0, 0, visited, m, n, k);
    }
private:
    int dfs(int i, int j, int si, int sj, vector<vector<bool>> &visited, int m, int n, int k) {
        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, visited, m, n, k) +
                   dfs(i, j + 1, si, (j + 1) % 10 != 0 ? sj + 1 : sj - 8, visited, m, n, k);
    }
};

0 赞同 0 条回复

花老爷普通 2023年7月15日下午5:24

模拟
时间：O(mn)
空间：O(mn)

class Solution {
    public int movingCount(int m, int n, int k) {
        int ans = 0;
        boolean[][] seen = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            if (getSum(i, 0) <= k) {
                seen[i][0] = true;
                ans++;
            } else {
                break;
            }
        }
        for (int i = 1; i < n; i++) {
            if (getSum(0, i) <= k) {
                seen[0][i] = true;
                ans++;
            } else {
                break;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (getSum(i, j) <= k && (seen[i - 1][j] || seen[i][j - 1])) {
                    seen[i][j] = true;
                    ans++;
                }
            }
        }
        return ans;
    }

    private int getSum(int m, int n) {
        int ans = 0;
        while (m > 0) {
            ans += m % 10;
            m /= 10;
        }
        while (n > 0) {
            ans += n % 10;
            n /= 10;
        }
        return ans;
    }
}

0 赞同 0 条回复

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

共以下 13 个回答

MY

# 回答此问题取消回复

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

共以下 13 个回答

MY

# 回答此问题 取消回复

# 回答此问题取消回复