作者:翟天保Steven
版权声明:著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处
地上有一个 rows 行和 cols 列的方格。坐标从 [0,0] 到 [rows-1,cols-1] 。一个机器人从坐标 [0,0] 的格子开始移动,每一次只能向左,右,上,下四个方向移动一格,但是不能进入行坐标和列坐标的数位之和大于 threshold 的格子。 例如,当 threshold 为 18 时,机器人能够进入方格 [35,37] ,因为 3+5+3+7 = 18。但是,它不能进入方格 [35,38] ,因为 3+5+3+8 = 19 。请问该机器人能够达到多少个格子?
数据范围: 0≤threshold≤15 ,1≤rows,cols≤100
进阶:空间复杂度O(nm) ,时间复杂度O(nm)
输入:
10,1,100
返回值:
29
说明:
[0,0],[0,1],[0,2],[0,3],[0,4],[0,5],[0,6],[0,7],[0,8],[0,9],[0,10],[0,11],[0,12],[0,13],[0,14],[0,15],[0,16],[0,17],[0,18],[0,19],[0,20],[0,21],[0,22],[0,23],[0,24],[0,25],[0,26],[0,27],[0,28] 这29种,后面的[0,29],[0,30]以及[0,31]等等是无法到达的
本题是回溯法的经典题目,也常用于解决迷宫问题。思路如下:
class Solution {
public:
// 移动计数
int movingCount(int threshold, int rows, int cols) {
if(rows <= 0 || cols <= 0 || threshold < 0)
return 0;
// 记录位置是否被走过
vector<vector<bool>> flags(rows, vector<bool>(cols, false));
// 起点出发,递归回溯
int count = moving(threshold, rows, cols, 0, 0, flags);
return count;
}
// 移动
int moving(int threshold, int rows, int cols, int row, int col, vector<vector<bool>>& flags){
if(row < 0 || col < 0 || row >= rows || col >= cols || flags[row][col]
|| decompose(row) + decompose(col) > threshold )
return 0;
// 此点通
flags[row][col] = true;
// 四向移动
return 1 + moving(threshold, rows, cols, row - 1, col, flags)
+ moving(threshold, rows, cols, row + 1, col, flags)
+ moving(threshold, rows, cols, row, col - 1, flags)
+ moving(threshold, rows, cols, row, col + 1, flags);
}
// 数字分解
int decompose(int num){
int sum = 0;
while(num > 0){
sum += num % 10;
num /= 10;
}
return sum;
}
};
联系客服