原创

每日一题-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; };

本文于   2020/4/8 下午  发布在  数学与算法  分类下,当前已被围观  316  次

相关标签: 算法与数学 每日一题

永久地址: https://huhuang.net/article/8

版权声明: 自由转载-署名-非商业性使用   |   Creative Commons BY-NC 3.0 CN