原创
每日一题-13. 机器人的运动范围
问题:
地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),也不能进入行坐标和列坐标的数位之和大于k的格子。 例如,当k为18时,机器人能够进入方格 [35, 37] ,因为3+5+3+7=18。但它不能进入方格 [35, 38],因为3+5+3+8=19。请问该机器人能够到达多少个格子?
示例 1:
输入:m = 2, n = 3, k = 1
输出:3
示例 2:
输入:m = 3, n = 1, k = 0
输出:1
提示:
1 <= n,m <= 100
0 <= k <= 20
解题思路
这道题是典型的矩阵搜索问题。此类问题通常可使用 深度优先搜索(DFS) 或 广度优先搜索(BFS) 解决。
DFS
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
var movingCount = function (m, n, k) {
var matrix = new Array(m);
var DFS = function (i, j) {
if (!matrix[i]) {
matrix[i] = new Array(n)
}
if (i < 0 || i >= m || j < 0 || j >= n || (parseInt(i / 10) + i % 10 + parseInt(j / 10) + j % 10) > k || matrix[i][j]) {
return 0
}
matrix[i][j] = true;
return DFS(i + 1, j) + DFS(i, j + 1) + 1;
}
return DFS(0, 0);
};
BFS
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
var movingCount = function (m, n, k) {
var matrix = new Array(m);
var queue = new Array();
queue.push([0, 0, 0]);
var count = 0;
while (queue.length > 0) {
var x = queue.shift();
var i = x[0],
j = x[1],
number = x[2];
if (!matrix[i]) {
matrix[i] = new Array(n)
}
if (i < 0 || i >= m || j < 0 || j >= n || k < number || matrix[i][j]) continue;
matrix[i][j] = true;
count++;
queue.push([i + 1, j, parseInt((i + 1) / 10) + (i + 1) % 10 + parseInt(j / 10) + j % 10]);
queue.push([i, j + 1, parseInt(i / 10) + i % 10 + parseInt((j + 1) / 10) + (j + 1) % 10]);
}
return count;
};
0 条看法
0 人喜欢 最新 最热
期待你的捷足先登