C#LeetCode刷题之#874-模拟行走机器人​​​​​​​（Walking Robot Simulation）

-2：向左转 90 度
-1：向右转 90 度
1 <= x <= 9：向前移动 x 个单位长度

• 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.

Input: commands = [4,-1,3], obstacles = []

Output: 25

Explanation: robot will go to (3, 4)

Input: commands = [4,-1,4,-2,4], obstacles = [[2,4]]

Output: 65

Explanation: robot will be stuck at (1, 4) before turning left and going to (1, 8)

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.

```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);

}

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) {
}
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) {
}
//解析每个命令
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;
}
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;
}

}```

```25
65
125```