问题
该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/4038 访问。
机器人在一个无限大小的网格上行走，从点 (0, 0) 处开始出发，面向北方。该机器人可以接收以下三种类型的命令：
-2：向左转 90 度
-1：向右转 90 度
1 <= x <= 9：向前移动 x 个单位长度
在网格上有一些格子被视为障碍物。
第 i 个障碍物位于网格点 (obstacles[i][0], obstacles[i][1])
如果机器人试图走到障碍物上方，那么它将停留在障碍物的前一个网格方块上，但仍然可以继续该路线的其余部分。
返回从原点到机器人的最大欧式距离的平方。
提示：
- 0 <= commands.length <= 10000
- 0 <= obstacles.length <= 10000
- -30000 <= obstacle[i][0] <= 30000
- -30000 <= obstacle[i][1] <= 30000
- 答案保证小于 2 ^ 31
A robot on an infinite grid starts at point (0, 0) and faces north. The robot can receive one of three possible types of commands:
-2: turn left 90 degrees
-1: turn right 90 degrees
1 <= x <= 9: move forward x units
Some of the grid squares are obstacles.
The i-th obstacle is at grid point (obstacles[i][0], obstacles[i][1])
If the robot would try to move onto them, the robot stays on the previous grid square instead (but still continues following the rest of the route.)
Return the square of the maximum Euclidean distance that the robot will be from the origin.
Note:
- 0 <= commands.length <= 10000
- 0 <= obstacles.length <= 10000
- -30000 <= obstacle[i][0] <= 30000
- -30000 <= obstacle[i][1] <= 30000
- The answer is guaranteed to be less than 2 ^ 31.
示例
该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/4038 访问。
public class Program {
public static void Main(string[] args) {
var commands = new int[] { 4, -1, 3 };
var obstacles = new int[][] { };
var res = RobotSim(commands, obstacles);
Console.WriteLine(res);
commands = new int[] { 4, -1, 4, -2, 4 };
obstacles = new int[][] { new int[] { 2, 4 } };
res = RobotSim2(commands, obstacles);
Console.WriteLine(res);
commands = new int[] { 1, -1, 5, -2, 9 };
obstacles = new int[][] { new int[] { 1, 2 } };
res = RobotSim3(commands, obstacles);
Console.WriteLine(res);
Console.ReadKey();
}
public enum Direction {
Up = 0,
Left = 1,
Down = 2,
Right = 3
}
private static void ComputerDirection(ref Direction direction, int cmd) {
if(cmd == -2) {
//向左转 90 度
if(direction == Direction.Right) {
direction = Direction.Up;
} else direction++;
} else if(cmd == -1) {
//向右转 90 度
if(direction == Direction.Up) {
direction = Direction.Right;
} else direction--;
}
}
public static int RobotSim(int[] commands, int[][] obstacles) {
//传统解法
var x = 0;
var y = 0;
var move = 0;
var curDirection = Direction.Up;
var distance = 0;
var obset = new HashSet<KeyValuePair<int, int>>();
foreach(var obs in obstacles) {
obset.Add(new KeyValuePair<int, int>(obs[0], obs[1]));
}
foreach(var cmd in commands) {
if(cmd == -1 || cmd == -2) ComputerDirection(ref curDirection, cmd);
else {
move = 0;
switch(curDirection) {
case Direction.Up:
while(++move <= cmd) {
if(obset.Contains(new KeyValuePair<int, int>(x, y + move))) break;
}
y += --move;
break;
case Direction.Left:
while(++move <= cmd) {
if(obset.Contains(new KeyValuePair<int, int>(x - move, y))) break;
}
x -= --move;
break;
case Direction.Down:
while(++move <= cmd) {
if(obset.Contains(new KeyValuePair<int, int>(x, y - move))) break;
}
y -= --move;
break;
case Direction.Right:
while(++move <= cmd) {
if(obset.Contains(new KeyValuePair<int, int>(x + move, y))) break;
}
x += --move;
break;
default:
break;
}
distance = Math.Max(distance, x * x + y * y);
}
}
return distance;
}
public static int RobotSim2(int[] commands, int[][] obstacles) {
//优化方向的解析
//可以理解为方向向量
var direc = new List<KeyValuePair<int, int>>
{
{ new KeyValuePair<int, int>(0, 1) }, //上
{ new KeyValuePair<int, int>(1, 0) }, //右
{ new KeyValuePair<int, int>(0, -1) }, //下
{ new KeyValuePair<int, int>(-1, 0) } //左
};
//障碍物哈希表，加速障碍物的判定
var obset = new HashSet<KeyValuePair<int, int>>();
//x 值和 y 值计数
var x = 0;
var y = 0;
//最大距离
var distance = 0;
//方向值
var direction = 0;
//初始化障碍物
foreach(var obs in obstacles) {
obset.Add(new KeyValuePair<int, int>(obs[0], obs[1]));
}
//解析每个命令
foreach(var cmd in commands) {
//0，1，2，3代表 4个方向，请自行分析
if(cmd == -2) {
//向左转 90 度
direction = (direction + 3) % 4;
} else if(cmd == -1) {
//向右转 90 度
direction = (direction + 1) % 4;
} else {
//先记录命令的值，因为 cmd 为迭代变量，C#语法规定不允许变更
var count = cmd;
//在水平方向或垂直方向上分析障碍物
//记数每次 -1，直接 0 时为止
//count-- 不能写成 --count，请自行分析
while(count-- > 0) {
//记录移动到的位置
var dx = x + direc[direction].Key;
var dy = y + direc[direction].Value;
//障碍物判定，使用哈希加速查找
//因为哈希查找为 O(1) 时间复杂度，即为常量时间复杂度
if(obset.Contains(new KeyValuePair<int, int>(dx, dy))) {
//若包含说明有障碍物，直接退出循环
break;
}
//若不包含说明没有障碍物
//更新 x 和 y 的值
x = dx;
y = dy;
//每次计算距离
distance = Math.Max(distance, x * x + y * y);
}
}
}
//返回最大距离
return distance;
}
public static int RobotSim3(int[] commands, int[][] obstacles) {
//基本思路同 RobotSim2
//此解法参考 LeetCode 官方【阅读】模块
//实测效率略快于 RobotSim2 的解法
var direc = new List<KeyValuePair<int, int>>
{
{ new KeyValuePair<int, int>(0, 1) },
{ new KeyValuePair<int, int>(1, 0) },
{ new KeyValuePair<int, int>(0, -1) },
{ new KeyValuePair<int, int>(-1, 0) }
};
var obset = new HashSet<long>();
var x = 0;
var y = 0;
var distance = 0;
var direction = 0;
//优化编码
foreach(var obs in obstacles) {
long ox = (long)obs[0] + 30000;
long oy = (long)obs[1] + 30000;
obset.Add((ox << 16) + oy);
}
foreach(var cmd in commands) {
if(cmd == -2) {
direction = (direction + 3) % 4;
} else if(cmd == -1) {
direction = (direction + 1) % 4;
} else {
var count = cmd;
while(count-- > 0) {
var dx = x + direc[direction].Key;
var dy = y + direc[direction].Value;
long code = (((long)dx + 30000) << 16) + ((long)dy + 30000);
//优化障碍物判定
if(obset.Contains(code)) {
break;
}
x = dx;
y = dy;
distance = Math.Max(distance, x * x + y * y);
}
}
}
return distance;
}
}以上给出3种算法实现，以下是这个案例的输出结果：
该文章的最新版本已迁移至个人博客【比特飞】，单击链接 https://www.byteflying.com/archives/4038 访问。
25
65
125分析：
设命令和障碍物的数量分别为 m 和 n，那么以上3种算法的时间复杂度应当均为 。