机器人走格子

绝地灬酷狼 2023-02-22 12:17 1阅读 0赞

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

dfs：

class Solution {
        
    public:
        int sum(int i, int j){
        
            int count = 0;
            while(i > 0) {
        
                count = count + i%10;
                i = i/10;
            }
            while(j > 0) {
        
                count = count + j%10;
                j = j/10;
            }
            return count;
        }
        int num = 0;
        int dir[5] = {
        1, 0, -1, 0, 1};
        void dfs(int *&m, int threshold, int rows, int cols, int i, int j){
        
            if(i < 0 || i >= rows || j < 0 || j >= cols || sum(i, j) > threshold || m[i*cols+j] == 1) return;
            
            num++;
            m[i*cols+j] = 1;
            
            for(int k = 0; k < 4; k++) dfs(m, threshold, rows, cols, i+dir[k], j+dir[k+1]);
        }
        
        int movingCount(int threshold, int rows, int cols)
        {
        
            int *matrix = new int[rows*cols];
            for(int i = 0; i < rows*cols; i++) matrix[i] = 0;
            
            dfs(matrix, threshold, rows, cols, 0, 0);
            return num;
        }
    };

bfs：

class Solution {
        
    public:
        int sum(int i, int j){
        
            int count = 0;
            while(i > 0) {
        
                count = count + i%10;
                i = i/10;
            }
            while(j > 0) {
        
                count = count + j%10;
                j = j/10;
            }
            return count;
        }
        
        int movingCount(int threshold, int rows, int cols)
        {
        
            int num = 0;
            int dir[5] = {
        1, 0, -1, 0, 1};
            int *matrix = new int[rows*cols];
            for(int i = 0; i < rows*cols; i++) matrix[i] = 0;
            
            queue<pair<int, int> > q;
            if(rows > 0 && cols > 0 && threshold >= 0)
            {
        q.push({
        0,0});
            matrix[0] = 1;}
            
            while(!q.empty()) {
        
                pair<int, int> p = q.front();
                for(int i = 0; i < 4; i++) {
        
                    if(sum(p.first+dir[i],p.second+dir[i+1]) <= threshold && \
                      matrix[(p.first+dir[i])*cols+p.second+dir[i+1]] == 0 && \
                      p.first+dir[i] >= 0 && p.first+dir[i] < rows && \
                      p.second+dir[i+1] >= 0 && p.second+dir[i+1] < cols) {
        
                        q.push({
        p.first+dir[i],p.second+dir[i+1]});
                        matrix[(p.first+dir[i])*cols+p.second+dir[i+1]] = 1;
                    }
                }
                q.pop();
                num++;
            }
            return num;
        }
    };

开二位数组：

int mark[rows][cols];
    memset(mark, -1, sizeof(mark));