class Solution
{
public:
    int get_sum(pair<int, int> p)
    {
        int s = 0;
        while (p.first)
        {
            s += p.first % 10; //个位
            p.first /= 10;  //十位移到个位上
        }
        while (p.second)
        {
            s += p.second % 10;
            p.second /= 10;
        }
        return s;
    }
    int movingCount(int threshold, int rows, int cols)  //行rows，列cols
    {
        if (!rows || !cols) return 0;  //为0，则方格不存在
        queue<pair<int, int>> q;
        vector<vector<bool>> st(rows, vector<bool>(cols, false)); //生成一个布尔类型的二维变长数组，并全部初始化为false

        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};  //左下右上

        int res = 0;
        q.push({0, 0}); //第一个点入队，从队尾插入
        while (q.size())
        {
            auto t = q.front(); //选择队头的点进行判断
            q.pop();  //当前选择的点出队，队头弹出
            if (st[t.first][t.second] || get_sum(t) > threshold) continue; //如果这个点已经计算过了或者数位之和大于k则continue
            res++;  //进入到这一步的格子符合要求，结果+1
            st[t.first][t.second] = true;
            for (int i = 0; i < 4; i++)
            {
                int x = t.first + dx[i], y = t.second + dy[i];
                //这里可能出现重复入队的情况，但是后面if会筛掉已经判断过的点
                if (x >= 0 && x < rows && y >= 0 && y < cols) q.push({x, y});
            }           
        }
        return res;  
    }
}

加了标注，最后class{}外少一个；

为什么不使用数组模拟呢，不是更快吗

边界的时候很难code的

直接按题意写

class Solution {
public:
    int movingCount(int threshold, int rows, int cols)
    {
        if(rows == 0 || cols == 0) return 0;
        bool st[50][50] = {false};
        int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
        queue<pair<int, int>> q;
        q.push({0, 0});
        int s = 1;
        while(q.size())
        {
            auto t = q.front();
            q.pop();
            int x = t.first, y = t.second;
            st[x][y] = true;
            for(int i = 0; i < 4; i ++)
            {
                int a = x + dx[i], b = y + dy[i];
                if(a < 0 || a >= rows || b < 0 || b >= cols) continue;
                if(st[a][b]) continue;
                int res = 0;
                int a1 = a, b1 = b;
                while(a1)
                {
                    res += a1 % 10;
                    a1 /= 10;
                }
                while(b1)
                {
                    res += b1 % 10;
                    b1 /= 10;
                }
                if(res <= threshold)
                {
                    st[a][b] = true;
                    s ++;
                    q.push({a, b});
                }
            }
        }
        return s;
    }
};

// Java
class Solution {

  int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

  public int movingCount(int threshold, int rows, int cols) {
    if (rows * cols == 0) return 0;
    if (threshold == 0) return 1;
    return dfs(0, 0, rows, cols, threshold, new boolean[rows][cols]);
  }

  int bSum(int n) {
    int s = 0;
    while (n > 0) {
      s += n % 10;
      n /= 10;
    }
    return s;
  }

  int dfs(int x, int y, int n, int m, int k, boolean v[][]) {
    if (x < 0 || x >= n || y < 0 || y >= m
      || v[x][y] || bSum(x) + bSum(y) > k) return 0;
    v[x][y] = true;

    int c = 1;
    for (int i = 0; i < 4; i++)
      c += dfs(x + dx[i], y + dy[i], n, m, k, v);
    return c;
  }
}

为什么这种两层for循环枚举所有的点，当数据大了之后就不对了呢？不是时间复杂度的问题
求大佬解答
### 算法1
##### (暴力枚举) $O(n^2)$
class Solution {
public:
int movingCount(int threshold, int rows, int cols)
{ int ans=0;
for(int i=0;i[HTML_REMOVED]=10&&j<10){
sum=sum+j+i%10+i/10;
if(sum<=threshold){
ans;
}
}
if(j>=10&&i<10){
sum=sum+i+j%10+j/10;
if(sum<=threshold){
ans;
}
}
if(i>=10&&j>=10){
sum=sum+j%10+j/10+i%10+i/10;
if(sum<=threshold){
ans++;
}
}
}
}
return ans;
}
};

因为机械人只能一步一步走 枚举所有点会把跳跃的点一起算进去 但实际上机械人是走不到那里去的

后面的时候就理解了，歇歇咯

谢谢咯

class Solution {

public int movingCount(int threshold, int rows, int cols)
{
    int[][] f = new int[rows][cols];
    int res = 0;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (get(i) + get(j) > threshold) continue;
            if (i == 0 && j == 0) f[i][j] = 1;
            else {
                if (i > 0) f[i][j] |= f[i - 1][j];
                if (j > 0) f[i][j] |= f[i][j - 1];
            }
            res += f[i][j];
        }
    }
    return res;

}

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

}

class Solution {
public:
    int parse(int i){
        int ret = 0;
        while(i){
            ret += i % 10;
            i = i / 10;
        }
        return ret;
    }
    bool check(int i, int j, int threshold){
        return parse(i) + parse(j) <= threshold;
    }

    void dfs(int i, int j, int threshold, int rows, int cols, vector<vector<int>>& visted, int& count){
        if(i < 0 || i >= rows || j < 0 || j >= cols) return;
        if(visted[i][j]) return;
        if(check(i, j, threshold)) {
            count++; visted[i][j] = 1;
            dfs(i + 1, j, threshold, rows, cols, visted, count);
            dfs(i - 1, j, threshold, rows, cols, visted, count);
            dfs(i, j - 1, threshold, rows, cols, visted, count);
            dfs(i, j + 1, threshold, rows, cols, visted, count);
        }else{
            return;
        }

    }

    int movingCount(int threshold, int rows, int cols)
    {
        int ret = 0;
        vector<vector<int>> visted(rows, vector<int>(cols, 0));
        dfs(0, 0, threshold, rows, cols, visted, ret);
        return ret;
    }
};

这个题dfs不会出错吗？

class Solution {
public:
    int movingCount(int k, int m, int n)
    {
        int count = 0, sum1 = 0, sum2 = 0;  //sum1，sum2分别是两个数的数位和
        int r = 10;
        if (k >= 9) {
            // 从9开始接通的范围 round 为20*20的格子，当然由于 n 和 m 的限制你可能用不到
            // 从10开始接通的范围 round 为30*30的格子，当然由于 n 和 m 的限制你可能用不到
            //......
            //上面有图
            r = (k - 7) * 10;   
        }
        for (int i = 0; i < m; i++) {
            //接通后可以随意看到一个符合的数 count++ 。
            for (int j = 0; j < n && i + j < r; j++) {              
                sum1 = i / 10 + i % 10;
                sum2 = j / 10 + j % 10;
                if (sum1 + sum2 <= k) {
                    count++;
                }
            }
        }               
        return count;
    }
};

铁汁，这个接通的范围要怎么理解，没看明白orz

class Solution {
public:
int movingCount(int threshold, int rows, int cols)
{
if(rows==0||cols==0)
return 0;
int res=0;
int array[50][50];
DFS(threshold,rows,cols,0,0,array,&res);
return res;
}
void DFS(int k,int m,int n,int x,int y,int (array)[50],int res){
int a=x/10,b=x%10,c=y/10,d=y%10;
if(a+b+c+d>k)
return;
(*res);
array[x][y]=1;
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
for(int i=0;i<4;i){
int q=x+dx[i],w=y+dy[i];
if(q>=0&&q[HTML_REMOVED]=0&&w<n&&array[q][w]!=1)
DFS(k,m,n,q,w,array,res);
}
}
};

为什么这里先判断再入队结果不对？求解答

class Solution {
    int[] dx = {1, 0, -1, 0};
    int[] dy = {0, 1, 0, -1};
    public int movingCount(int threshold, int rows, int cols){
        if (rows == 0 || cols == 0) return 0;
        boolean[][] visited = new boolean[rows][cols];
        Deque<int[]> q = new LinkedList<>();
        int res = 0;
        q.offer(new int[]{0, 0});
        while (q.size() > 0) {
            int[] a = q.poll();
            int x = a[0], y = a[1];
            visited[x][y] = true;
            res ++;
            for (int i = 0; i < 4; i ++) {
                int u = x + dx[i], v = y + dy[i];
                if (u < 0 || u >= rows || v < 0 || v >= cols || visited[u][v]) continue;
                if (u % 10 + u / 10 + v % 10 + v / 10 > threshold) continue;
                q.offer(new int[]{u, v});
            }
        }
        return res;
    }
}

你可以试试看打印出进入队列的x, y坐标就知道问题了，因为一些点可以被多次入队。我调的C++代码如下：

class Solution {
public:

    int get_sum(int x, int y) {
        int res = 0;
        while(x) res += x % 10, x /= 10;
        while(y) res += y % 10, y /= 10;
        return res;
    }

    int movingCount(int threshold, int rows, int cols)
    {
        if(!rows || !cols) return 0;

        vector<vector<bool>> st(rows, vector<bool>(cols));
        queue<pair<int, int>> q;
        q.push({0, 0});
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}, cnt = 0;

        while(q.size()) {
            auto t = q.front();
            q.pop();

            int x= t.first, y = t.second;
            //if(st[x][y] || get_sum(x, y) > threshold) continue;
            st[x][y] = true;
            cnt ++;
            cout << cnt << ':' << x << '|' << y << endl;

            for(int i = 0; i < 4; i ++) {
                int a = x + dx[i], b = y + dy[i];
                if(a >= 0 && a < rows && b >= 0 && b < cols && !st[a][b] && get_sum(a, b) <= threshold)
                    q.push({a, b});
            }
        }
        return cnt;
    }
}; 

只要加入队列的点，res都会++；
对于多个点的相同（合法正确）的邻点会多次入队列（入队前都是没有被访问的），导致重复计数
例如
0 1
2 3
1和2加入队列后，3会重复入队列多次

我做的时候就在思考这个问题，多谢解答

想问一下曼哈顿距离没法解决这个问题么？

请问为什么我这个代码在本地的VS跑结果是对的，在这里跑结果不对。
例子是$[3, 13, 14]$

class Solution {
public:
    int movingCount(int threshold, int rows, int cols)
    {
        int count = 0;
        for(int i = 0;i < rows; i++){
            for(int j = 0; j < cols; j++){
                int a = ceil(i);
                int b = ceil(j);
                if(a + b <= threshold) count++;
            }
        }
        return count;
    }
    int ceil(int x){
        if(x == 0) return 0;
        int sum = 0;
        if(x/10 == 0) return x;
        else{
            sum += x % 10;
            x /= 10;
        }
    }
};

你代码逻辑不对，比如点(11, 10)，机器人一次只能走一步，没有有效路径可以到达这个点，但是你的代码会把它算上

而且你的ceil最后好像没有返回sum

如果是广度优先遍历，又是从原点 (0,0) 开始走，那么每次只用判断右边的格子和下边的格子。不需要上下左右都判定一遍。

int[] dx = new int[]{0, 1};
int[] dy = new int[]{1, 0};
while (!queue.isEmpty()) {
    Node node = queue.poll();
    res++;
    for (int i = 0; i < 2; i++) {
        int x = node.first + dx[i];
        int y = node.second + dy[i];
        if (x >= 0 && x < m && y >= 0 && y < n && !visited[x][y] && isLess(x, y, k)) {
            queue.offer(new Node(x, y));
            visited[x][y] = true;
        }
    }
}

// 四个方向数组
int dx[]={-1,0,1,0},dy[]={0,1,0,-1};
// 标记数组。防止点重复访问
bool visited[110][110];

class Solution {
public:
    int movingCount(int m, int n, int k) {
        memset(visited,0,sizeof visited);
        int cnt=0;
        dfs(m,n,k,0,0,cnt);
        return cnt;
    }

    void dfs(int m,int n,int k,int i,int j,int& cnt)
    {
        // 无法到达(i,j)这个点
        if(work(i)+work(j)>k)return;
        // 可以到(i,j)这个点，则打标记和cnt+1
        visited[i][j]=true;   
        cnt++;
        // 进行4个方向的dfs
        for(int c=0;c<4;++c)
        {
            int x=i+dx[c],y=j+dy[c];
            if(x>=0&&x<m&&y>=0&&y<n&&!visited[x][y])
                dfs(m,n,k,x,y,cnt);
        }
    }

    // 计算各数位之和
    int work(int x)
    {
        int val=0;
        while(x)val+=x%10,x/=10;
        return val;
    }
};

老哥，要加一个 m和n都为0 就不用dfs了

你好，请问我这个哪里错了，报错看不懂。。。

class Solution {
public:

    int movingCount(int threshold, int rows, int cols)
    {   if(!rows || !cols) return 0;
        vector<vector<bool>> res(rows, vector<bool>(cols,false));
        return dfs(res, threshold, 0, 0);
    }
    int dfs(vector<vector<bool>> res, int k, int i, int j){
        if(res[i][j]) return 0;
        res[i][j] = true;
        if(i < 0 || i >= res.size() || j < 0 || j >= res[0].size()) return 0;
        if(get_sum(i,j) > k) return 0;
        return dfs(res, k, i + 1, j) + dfs(res, k, i, j + 1) + dfs(res, k, i, j + 1) + dfs(res ,k , i, j - 1) + 1;
    }

    int get_sum(int i, int j){
        int ans = 0;
        while(i){
            ans += i % 10;
            i /= 10; 
        }
        while(j){
            ans += j % 10;
            j /= 10;
        }
        return ans;  
    }
};

if(i < 0 || i >= res.size() || j < 0 || j >= res[0].size()) return 0;
这段应该在dfs的第一句吧

class Solution {
public:

int movingCount(int threshold, int rows, int cols)
{   if(!rows || !cols) return 0;
    vector<vector<bool>> res(rows, vector<bool>(cols,false));
    return dfs(res, threshold, 0, 0);
}
int dfs(vector<vector<bool>>&res, int k, int i, int j){
    if(i < 0 || i >= res.size() || j < 0 || j >= res[0].size()) return 0;
    if(get_sum(i,j) > k) return 0;
    if(res[i][j]==true) return 0;
    res[i][j] = true;
    return dfs(res, k, i + 1, j) + dfs(res, k, i, j + 1) + dfs(res, k, i, j + 1) + dfs(res ,k , i, j - 1) + 1;
}

int get_sum(int i, int j){
    int ans = 0;
    while(i){
        ans += i % 10;
        i /= 10; 
    }
    while(j){
        ans += j % 10;
        j /= 10;
    }
    return ans;  
}

};

新手问一个问题：普遍做法是上下左右四个方向搜，但这题是走（0，0）点开始，似乎只用右和下两个方向也可以，这样子做会优化时间复杂度吗？

不影响时间复杂度，因为绝大部分格子都需要搜4个方向。

确实只需要两个方向就可以遍历完全部的格子哈，相当于优化时间复杂度中的常数项

暴力流

class Solution {
    public int movingCount(int k, int rows, int cols){
        boolean[][] vis = new boolean[rows][cols] ;
        return dfs(k,0,0,vis) ;
    }
    public int dfs(int k,int i,int j,boolean[][] vis){
        if(i<0 || i >= vis.length || j<0 || j>=vis[0].length || vis[i][j] || (i/10+i%10+j/10+j%10)>k){
            return 0;
        }
        vis[i][j] = true ;
        return dfs(k,i+1,j,vis) + dfs(k,i-1,j,vis) + dfs(k,i,j-1,vis) + dfs(k,i,j+1,vis) + 1;
    }
}

不错！DFS也是可以的，时间复杂度也是 $O(nm)$。

为什么是这个，我还以为是指数级别的，hh

因为有 vis[i][j] 判重，所以每个点只会搜索一遍，一共只有 $O(nm)$ 个格子，所以总时间复杂度仍然是 $O(nm)$。

递归的时间复杂度不怎么会分析，听了y总回答，觉得很高兴

(i/10+i%10+j/10+j%10)>k)
i和j如果是123,这样能得到正确结果吗

这道题目的数据范围比较小，限定了n <= 50, m <= 50，所以i和j都在100以内。

你这个程序结果咋不对呀

我这个是java程序，你看看是不是语言弄错了

hhh，我用的c++改的

真的暴力= =

class Solution {
public:
    int movingCount(int threshold, int rows, int cols)
    {
        vector<vector<bool>> visited(rows, vector<bool>(cols));
        return dfs(threshold, 0, 0, visited);
    }
    int dfs(int th, int i, int j, vector<vector<bool>> vis){
        if(i < 0 || i >=vis.size() || j < 0 || j >= vis[i].size() || vis[i][j] ||(i/10+i%10+j/10+j%10)>th) return 0;
        vis[i][j]=true;
        return dfs(th,i+1, j, vis)+dfs(th,i-1, j, vis)+dfs(th,i, j-1, vis)+dfs(th,i, j+1, vis) + 1;
    }
};

仿照您的DFS代码，写的C++，不知道哪不对劲？

因为dfs会递归下去，参数传递的是形参，因此要在vis前面加个引用，表示这个数组的值已经修改

class Solution {
public:
    int movingCount(int threshold, int rows, int cols)
    {
        vector<vector<bool>> vis(rows, vector<bool>(cols));
        return dfs(threshold, 0, 0, vis);
    }
    int dfs(int th, int i, int j, vector<vector<bool>> &vis){
        if(i < 0 || i >=vis.size() || j < 0 || j >= vis[i].size() || vis[i][j] ||(i/10+i%10+j/10+j%10)>th) return 0;
        vis[i][j]=true;
        return dfs(th,i+1, j, vis)+dfs(th,i-1, j, vis)+dfs(th,i, j-1, vis)+dfs(th,i, j+1, vis) + 1;
    }
};

感谢您

很棒。

优秀

请问 这里DFS的为什么不用回溯呢 vis[i][j] = true

这里vis数组的作用是判重，避免重复搜索合法的节点，因此不需要回溯

是不是遍历完了四个方向之后也不需要往回走 所以不用回溯呢 新手对于回溯有点蒙

嗯，不要要往回走，只要往每个点4个方向一直搜就行

好的 谢谢DL

如果把整个棋盘当做一个状态，那就需要回溯；如果把棋盘中的每个点当做状态，就不需要回溯。

class Solution {
public:
    int movingCount(int threshold, int rows, int cols)
    {
        if(rows==0 || cols==0)  return 0;
        int count = 1;
        int ok[rows][cols] = {0};
        ok[0][0] = 1;
        for(int i = 0; i < rows; i++)
        {
            for(int j = 0; j < cols; j++)
            {
                //int m = i, n = j;
                int ad = i % 10 + i / 10 + j % 10 + j / 10;
                if(ad <= threshold && (ok[i-1][j] == 1 || ok[i][j-1] == 1))
                {
                    count++;
                    ok[i][j] = 1;
                }
            }
        }
        return count;
    }
};

这份代码有问题，数组可能会越界。

请问这个地方如果把下标改成从1开始是不是就可以了？

if (st[t.first][t.second] || get_sum(t) > threshold) continude;
灿哥，重刷剑指Offer时候，发现这里有点懵，为什么当该格子不符合要求时，是直接跳出循环，而不需要将它的邻接点加入队列呢？求指教hh

因为机器人只能从某个合法格子走进相邻的合法格子，不能走进非法格子。

啊，发现了，看题不仔细了，嘿嘿~