2019 年 LeetCode 杯全国秋季编程大赛 第 3 题,机器人大冒险,中等难度。

题目

原题链接

本次竞赛题目已公布在 LeetCode 题库,由此访问。

题目描述

力扣团队买了一个可编程机器人,机器人初始位置在原点 (0, 0)。小伙伴事先给机器人输入一串指令 command,机器人就会无限循环这条指令的步骤进行移动。指令有两种:

  1. U: 向 y 轴正方向移动一格
  2. R: 向 x 轴正方向移动一格。

不幸的是,在 xy 平面上还有一些障碍物,他们的坐标用 obstacles 表示。机器人一旦碰到障碍物就会被损毁。

给定终点坐标 (x, y),返回机器人能否完好地到达终点。如果能,返回 true;否则返回 false

示例 1:

输入:command = "URR", obstacles = [], x = 3, y = 2
输出:true
解释:U(0, 1) -> R(1, 1) -> R(2, 1) -> U(2, 2) -> R(3, 2)。

示例 2:

输入:command = "URR", obstacles = [[2, 2]], x = 3, y = 2
输出:false
解释:机器人在到达终点前会碰到(2, 2)的障碍物。

示例 3:

输入:command = "URR", obstacles = [[4, 2]], x = 3, y = 2
输出:true
解释:到达终点后,再碰到障碍物也不影响返回结果。

限制:

  1. 2 <= command 的长度 <= 1000
  2. command 由 U,R 构成,且至少有一个 U,至少有一个 R
  3. 0 <= x <= 1e9, 0 <= y <= 1e9
  4. 0 <= obstacles 的长度 <= 1000
  5. obstacles[i] 不为原点或者终点

解题

AC 样例

/**
 * @param {string} command
 * @param {number[][]} obstacles
 * @param {number} x
 * @param {number} y
 * @return {boolean}
 */
var robot = function(command, obstacles, x, y) {
  const point = [0, 0];
  let i = 0;
  // 过滤有效障碍点
  obstacles = obstacles.filter(points => points[0]<=x && points[1]<=y);
  
  // 循环终止条件:x y 超过目标点位
  while(point[0] <= x && point[1] <= y) {
    const index = i%command.length;
    
    // 循环指令
    if(command[index] === 'U') point[1] += 1;
      else point[0] += 1;
    // 障碍点识别
    if(obstacles.filter(points => points[0]==point[0] && points[1]==point[1]).length) return false;
    // 目标点识别
    if(point[0] == x && point[1] == y) return true;

    i++;
  }
  // 无法到达时返回
  return false;
};

思路分析

根据题目要求,可知机器人出发点坐标为 (0, 0),按指令循环移动,每步移动一个单位。已知指令后可以推导机器人每步点位,当横纵坐标位置到达目标点 (x, y) 时视为成功,否则失败。初始化一个值为 [0, 0] 的数组,其 0 位表示 x 轴坐标,1 位表示 y 轴坐标。当指令 R 时数组 0 位加一,当指令 U 时数组 1 位加一,通过数值变化表示点位运动。

首先检查机器人正常工作时能否到达 (x, y)。需要推导机器人从 (0, 0) 运动至横坐标等于 x 或纵坐标等于 y 时的所有点位,判断最终点位是否是 (x, y) 目标点。如最终点位与目标不符,则认为机器人正常工作时即无法到达目标点,返回值始终为 false

在确认机器人无干扰工作可以到达目标点后,对运动期间点位是否存在障碍点做识别。当运动期间点位存在障碍点,则机器人无法到达目标点,提前返回 false

语法点

对数组进行条件筛选时,可以优先使用条件过滤函数。

// Array 原型提供的过滤器函数
Array.prototype.filter();

// filter() 语法
arr.filter(callback(element[, index[, array]])))

调用 filter() 方法需要一个回调函数参数用于条件筛选,当回调函数返回值为 true 时,被处理数据符合筛选条件,予以保留,否则不保留。回调函数必须包含一个 element 参数,表示当前被处理数据。可选参数 index 表示当前被处理数据的数组内索引号。可选参数 array 用于表示被处理数组本身,可参与回调函数的运算过程。