JZ66 机器人的运动范围

题意分析

• 给我们一张二维的地图，初始的位置在（0,0），可以往上下左右四个方向进行移动。但是移动需要需要满足如下条件：

  • 不能超过地图的边界
  • 移动的位置的坐标的数位的数字的和不能超过给定的数字

思路分析

• 这个题目我主要用的是BFS和DFS这两个算法进行求解。可以结合这个图进行理解。

解法一 BFS

• 我们知道，对于每一个位置，我们可以选择四个方向进行移动，由于这个题目没有其他特殊的限制，所以我们可以进行广度优先遍历。我们首先将初始的位置保存到一个队列里面，然后从这个队列开始向外进行扩展，当我们扩展之前我们需要判断需要入队的位置是否符合题目的条件，如果满足，那么我们可以直接将这个位置入队。然后继续想之后的位置进行同样的拓展。直到整个队列都为空的。
• 代码如下
  • 每个位置需要遍历一遍，所以时间复杂度为O(rows*cols)
  • 对于每个位置需要我们存储，所以空间复杂度为O(rows*cols)

class Solution {
public:
    int X[4]={0,0,1,-1};
    int Y[4]={1,-1,0,0};
    bool vis[105][105];  // 用于判断每个位置被访问的情况
// getsum 是获取一个数的数位之和的一个函数
    int getsum(int x){
        int sum=0;
        while(x){
            sum+=x%10;
            x/=10;
        }
        return sum;
    }
// 定义每个状态的结构，就是x和y坐标
    struct node{
        int x,y;
    }Node;
    queue<node> q;
    int movingCount(int threshold, int rows, int cols) {
    // 初始化一个队列，将最开始的点放入整个队列里面
        Node.x=Node.y=0;
        q.push(Node);
        vis[0][0]=true;
        int ans=1;
        while(!q.empty()){
            node now=q.front();
            q.pop();
        // 判断上下左右四个方向是否可行
            for(int i=0;i<4;i++){
                int nowx=now.x+X[i];
                int nowy=now.y+Y[i];
                // 将不符合条件的剔除
                if(nowx>rows-1||nowx<0||nowy>cols-1||nowy<0) continue;
                if(vis[nowx][nowy]||getsum(nowx)+getsum(nowy)>threshold) continue;
                Node.x=nowx,Node.y=nowy;
                ans++;
                vis[nowx][nowy]=true;
                q.push(Node);
            }
        }
        return ans;
    }
};

解法二 DFS

• 这种解法就是上一个解法的变形，只是写法不一样，其他的实质还是一样的。具体的思路和BFS也是一样的。就是我们不断递归判断四个方向的情况，知道不符合条件即可。不过这种解法也是有缺点的，就是如果递归太深的话会造成爆栈。这个是要注意的。

• 代码如下

  • 每个位置需要遍历一遍，所以时间复杂度为O(rows*cols)
  • 对于每个位置需要我们存储，所以空间复杂度为O(rows*cols)

    class Solution {
    public:
    int ans=0;
    bool vis[120][120];
    // getsum用来计算某一个数的所有的数位的和
    int getsum(int x){
      int sum=0;
      while(x){
          sum+=x%10;
          x/=10;
      }
      return sum;
    }
    void dfs(int r,int w,int rows,int cols,int threshold){
      // 递归出口
      if(r<0||r>rows-1||w<0||w>cols-1){
          return;
      }
      if(vis[r][w]==true||getsum(r)+getsum(w)>threshold){
          return ;
      }
      // 更新状态
      vis[r][w]=true;
      ans++;
      // 不断递归四个方向
      dfs(r+1,w,rows,cols,threshold);
      dfs(r,w+1,rows,cols,threshold);
      dfs(r-1,w,rows,cols,threshold);
      dfs(r,w-1,rows,cols,threshold);
    }
    int movingCount(int threshold, int rows, int cols) {
      dfs(0,0,rows,cols,threshold);
      return ans;
    }
    };