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

将上下左右四个方向，可以简化为往右或者往下，因为机器人是从[0][0]出发的 每到一个新的格子，就将visited[][]标记为true

用dfs走完所有格子，然后统计visited中true的个数，即为机器人能走的格子数，返回即可。

每个格子只检测一边，时间复杂度mn

需要一个visited数组记录每个格子的访问情况，空间复杂度mn

class Solution {
public:
	int movingCount(int threshold, int rows, int cols) {
		//初始化
		m_rows = rows; m_cols = cols; m_th = threshold; m_num = 0;
		for (int i = 0; i < rows; i++) {//初始化访问标记数组
			visited.emplace_back(vector<bool>());
			for (int j = 0; j < cols; j++)
				visited[i].emplace_back(false);
		}
		//
		dfs(0, 0);
		for (int i = 0; i < rows; i++) //统计为true的格子数
			for (int j = 0; j < cols; j++)
				if (visited[i][j])m_num++;
		
		return m_num;
	}
private:
	int m_th;//阈值
	int m_num=0;//能走的格子总数
	int m_rows, m_cols;//网格最大长度宽度
	vector<vector<bool>>visited;
	//判断某个格子符合阈值要求，符合则返回true
	bool is_LessOrEqual_to_mth(int x, int y) {
		int sum = 0;
		while (x != 0) {
			sum += x % 10;
			x /= 10;
		}
		while (y != 0) {
			sum += y % 10;
			y /= 10;
		}
		return (sum <= m_th);
	}
	void dfs(int x, int y) {
		visited[x][y] = true;
		//向右走
		if (y < m_cols - 1 && !visited[x][y + 1] &&  is_LessOrEqual_to_mth(x, y + 1)) {
			dfs(x, y + 1);
		}
		//向下走
		if (x < m_rows - 1 && !visited[x + 1][y] &&  is_LessOrEqual_to_mth(x + 1, y)) {
			dfs(x + 1, y);
		}
	}

};