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

/* //方法一，深度优先遍历 class Solution { public: int movingCount(int threshold, int rows, int cols) { static int count=0; vector<vector> 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> 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 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;
}

};