题解 | #机器人的运动范围#
机器人的运动范围
https://www.nowcoder.com/practice/6e5207314b5241fb83f2329e89fdecc8
class Solution {
public:
int n=0,row=0,col=0;//记录合法数，当前行数、列数
int sum(int row,int col){
int sum_row=row>9?row/10+row%10:row;
int sum_col=col>9?col/10+col%10:col;
return sum_row+sum_col;
}
void dfs(int threshold, int rows, int cols, vector<vector<bool>> &visited){
if(visited[row][col] || sum(row,col)>threshold)//出口:不合法或者已访问
return;
visited[row][col]=true;n++;//访问当前结点，合法数加一
if(row<rows-1)//向下走
row++;dfs(threshold,rows,cols,visited);//继续判断接下来的结点是否合法
if(row>0)//向上走
row--;dfs(threshold,rows,cols,visited);
if(col<cols-1)//向右走
col++;dfs(threshold,rows,cols,visited);
if(col>0)//向左走
col--;dfs(threshold,rows,cols,visited);
}
int movingCount(int threshold, int rows, int cols) {
vector<vector<bool>> visited(rows,vector<bool>(cols));
dfs(threshold,rows,cols,visited);
return n;
}
};
