题解 | #机器人的运动范围#

/*
//方法一，深度优先遍历
class Solution {
public:
    int movingCount(int threshold, int rows, int cols) {
        static int count=0;
        vector<vector<int>> matrix(rows);  //0为没走过，-1为走不了，1为走过了
        for(int i=0;i<rows;i++)
        {
            matrix[i].resize(cols);
            for(int j=0;j<cols;j++)
                matrix[i][j]=0;
        }
        DFS(matrix,threshold,0,0,rows,cols,count);
        return count;
    }
    
    //采用深度优先遍历
    void DFS(vector<vector<int>> &matrix,int threshold,int i,int j,int rows,int cols,int &count)
    {
        if(i<0||i>=rows||j<0||j>=cols)  //超出界限
            return;
        int m1=i/10;
        int m2=i%10;
        int n1=j/10;
        int n2=j%10;
        if(matrix[i][j]==1)  //已访问过，不再访问
            return;
        else if(matrix[i][j]==-1)  //走不通
            return;
        else if(m1+m2+n1+n2<=threshold&&matrix[i][j]==0)  //未访问又走得通的
        {
            count++;
            matrix[i][j]=1;
            DFS(matrix,threshold,i,j+1,rows,cols,count);
            DFS(matrix,threshold,i,j-1,rows,cols,count);
            DFS(matrix,threshold,i-1,j,rows,cols,count);
            DFS(matrix,threshold,i+1,j,rows,cols,count);
            return;
         }
        else
        {
            matrix[i][j]=-1;  //未访问又走不通的，方格内值置为-1
            return;
        }
    }
};
*/

//方法二，广度优先遍历
class Solution {
public:
    struct NODE{
        int x,y;
    };
    int movingCount(int threshold, int rows, int cols)
    {
        int count=0;
        vector<vector<int>> matrix(rows);  //0为没走过，-1为走不了和为走过了
        for(int i=0;i<rows;i++)
        {
            matrix[i].resize(cols);
            for(int j=0;j<cols;j++)
                matrix[i][j]=0;
        }
        int X[4]={0,0,1,-1};
        int Y[4]={1,-1,0,0};
        NODE node={0,0};
        queue<NODE> q;
        q.push(node);
        matrix[0][0]=-1;
        while(!q.empty())
        {
            node=q.front();
            q.pop();
            count++;
            for(int i=0;i<4;i++)
            {
                int nodex=node.x+X[i];
                int nodey=node.y+Y[i];
                if(nodex<0||nodex>=rows||nodey<0||nodey>=cols)
                    continue;
                if(matrix[nodex][nodey]==-1)
                    continue;
                else if(getsum(nodex,nodey)>threshold)
                    matrix[nodex][nodey]=-1;
                else
                {
                    NODE now;
                    now.x=nodex;
                    now.y=nodey;
                    q.push(now);
                    matrix[nodex][nodey]=-1;
                }
            }
        }
        return count;
    }

    int getsum(int i,int j )
    {
        int m1=i/10;
        int m2=i%10;
        int n1=j/10;
        int n2=j%10;
        return m1+m2+n1+n2;
    }
};