机器人的运动范围

C++ 解法, 执行用时: 2ms, 内存消耗: 504KB, 提交时间: 2021-07-20

class Solution {
public:
    int movingCount(int threshold, int rows, int cols) {
        if(threshold < 0 || rows <= 0 || cols <= 0)
            return 0;
        bool * visited = new bool[rows*cols];
        
        for(int i=0; i < rows* cols; ++i)
            visited[i] = false;
        
        int count = movingCountCore(threshold, rows, cols, 0, 0 , visited);
        
        delete[] visited;
        
        return count;
    }
 private:
    int movingCountCore(int threshold , int rows, int cols, int row, int col, bool * visited)
    {
        int count = 0;
        if(check(threshold, rows, cols, row, col, visited))
        {
            visited[row* cols + col] = true;
            
            count = 1 +  movingCountCore(threshold, rows, cols, row - 1, col , visited)
                                +  movingCountCore(threshold, rows, cols, row, col - 1, visited)
                                +  movingCountCore(threshold, rows, cols, row + 1, col , visited)
                                + movingCountCore(threshold, rows, cols, row, col + 1 , visited);
        }
        
        return count;
    }
    
    bool check(int threshold , int rows, int cols, int row, int col, bool * visited)
    {
        if(row >= 0 && row < rows && col >= 0 && col < cols 
          && getDigitSum(row) + getDigitSum(col) <= threshold
          && !visited[row*cols + col])
            return true;
        return false;
    }
    
    int  getDigitSum(int number)
    {
        int  sum = 0;
        while(number > 0)
        {
            sum += number % 10;
            number /= 10;
        }
        return sum;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 504KB, 提交时间: 2021-07-20

class Solution {
public:
    int cal_th(int rows, int cols)
    {
        int result=0;
        while(rows>=10)
        {
            result= result+ rows % 10;
            rows = rows / 10;
        }
        result+=rows;
        
        while(cols>=10)
        {
            result= result+ cols % 10;
            cols = cols / 10;
        }
        result+=cols;
        return result;
    }
    void dfs(int threshold, int i, int j, vector<vector<int>> & arr)
    {
        int rows=arr.size();
        int cols=arr[0].size();
        if(i<0 || j<0 || i>=rows || j>=cols)
        {
            return;
        }
        if(threshold>=cal_th(i, j) && arr[i][j]==0)
        {
            arr[i][j]=1;
        }
        else
        {
            return;
        }
        dfs(threshold,  i-1, j,  arr);
        dfs(threshold,  i+1, j,  arr);
        dfs(threshold,  i, j-1,  arr);
        dfs(threshold,  i, j+1,  arr);
    }
    int movingCount(int threshold, int rows, int cols) {
        int result=0;
        vector<vector<int>>  arr(rows,vector<int>(cols,0));
        dfs(threshold,0,0,arr);
        for(int i=0;i<rows;i++)
        {
            for(int j=0;j<cols;j++)
            {
                if(arr[i][j]==1)
                {
                    result++;
                }
            }
        }
        return result;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 504KB, 提交时间: 2021-07-18

class Solution {
    int get(int a)
    {
        int res=0;
        for(;a;a/=10)
        {
            res+=a%10;
        }
        return res;
    }
public:
    int movingCount(int threshold, int rows, int cols) {
        if(!threshold)
            return 1;
        vector<vector<int>>vis(rows,vector<int>(cols,0));
        queue<pair<int, int >>q;
        q.push(make_pair(0, 0));
        vector<int> dx={0,1};
        vector<int> dy={1,0};
        vis[0][0]=1;
        int ans=1;
        while(!q.empty())
        {
            auto cur=q.front();
            q.pop();
            for(int i=0;i<2;i++)
            {
                int tx=cur.first+dx[i];
                int ty=cur.second+dy[i];
                if(tx<0 || tx>=rows || ty<0 || ty>=cols || vis[tx][ty] || get(tx)+get(ty)>threshold )
                    continue;
                vis[tx][ty]=1;
                q.push(make_pair(tx, ty));
                ans++;
            }
        }
        return ans;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 504KB, 提交时间: 2021-06-26

class Solution {
public:
    int movingCount(int threshold, int rows, int cols) {
        if(threshold < 0 || rows <=0 || cols <= 0)
            return 0;
        
        int result = 0;
        stack<pair<int,int>> p; //p用来记录坐标点，pair是将2个数据组合成一组数据
        vector<vector<bool>> grid(rows,vector<bool>(cols,false));//定义m行n列的方格，初始化都为false，表示未走过
        
        //BFS
        int dx[4] = {-1,0,1,0};
        int dy[4] = {0,1,0,-1};
        p.push({0,0}); //先把（0，0）点push进入，让循环开始
        while(p.size())
        {
            //把栈中的坐标拿出来进行判断
            pair<int,int> temp = p.top();
            p.pop();
            
            //如果这个格子已经走过即为true 或者 行列坐标的数位之和大于threshold，则continue继续当前循环
            if(grid[temp.first][temp.second] || getDigitSum(temp.first)+getDigitSum(temp.second) > threshold)
                continue;
            
            result ++;
            grid[temp.first][temp.second] = true; //符合要求的格子置为true，代表走过，防止回走重复计算
            
            for(int i=0; i<4; i++)
            {
                int a = temp.first+dx[i];
                int b = temp.second+dy[i];
                if(a >=0 && a < rows && b >=0 && b < cols)
                    p.push({a,b});
            }
        }
        return result;
    }
    
    int getDigitSum(int number)
    {
        int sum = 0;
        while(number > 0)
        {
            sum += number%10;
            number /= 10;
        }
        return sum;
    }
};

C++ 解法, 执行用时: 2ms, 内存消耗: 504KB, 提交时间: 2021-05-23

class Solution {
private:
    const int move[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
    vector<vector<bool>> visit;
    int res = 0;
public:
    int movingCount(int threshold, int rows, int cols) {
        visit = vector<vector<bool>>(rows,vector<bool>(cols,false));
        dfs(rows,cols,0,0,threshold);
        return res;
    }
    
    void dfs(const int rows, const int cols, int x, int y, const int target){
        res++;
        visit[x][y] = true;
        for(auto e:move){
            int xt = x + e[0];
            int yt = y + e[1];
            if(xt<0||xt>=rows||yt<0||yt>=cols)continue;
            if(visit[xt][yt])continue;
            if(getBit(xt)+getBit(yt)>target){
                visit[xt][yt] = true;
                continue;
            }
            dfs(rows,cols,xt,yt,target);
        }
    }
    
    int getBit(int num){
        int sum = 0;
        while(num>0){
            sum += (num%10);
            num /= 10;
        }
        return sum;
    }
};

详情