874. Walking Robot Simulation #

Problem #

A robot on an infinite XY-plane 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, or
1 <= k <= 9: move forward k units.

Some of the grid squares are obstacles. The ith obstacle is at grid point obstacles[i] = (xi, yi).

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 maximum Euclidean distance that the robot will be from the origin squared (i.e. if the distance is 5*, return* 25*)*.

Note:

North means +Y direction.
East means +X direction.
South means -Y direction.
West means -X direction.

Example 1:

Input: commands = [4,-1,3], obstacles = []
Output: 25
Explanation: The robot starts at (0, 0):
1. Move north 4 units to (0, 4).
2. Turn right.
3. Move east 3 units to (3, 4).
The furthest point away from the origin is (3, 4), which is 32 + 42 = 25 units away.

Example 2:

Input: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
Output: 65
Explanation: The robot starts at (0, 0):
1. Move north 4 units to (0, 4).
2. Turn right.
3. Move east 1 unit and get blocked by the obstacle at (2, 4), robot is at (1, 4).
4. Turn left.
5. Move north 4 units to (1, 8).
The furthest point away from the origin is (1, 8), which is 12 + 82 = 65 units away.

Constraints:

1 <= commands.length <= 104
commands[i] is one of the values in the list [-2,-1,1,2,3,4,5,6,7,8,9].
0 <= obstacles.length <= 104
3 * 104 <= xi, yi <= 3 * 104
The answer is guaranteed to be less than 231.

Problem Summary #

A robot walks on an infinite XY grid plane, starting from point (0, 0), facing north. The robot can receive the following three types of commands commands:

2: turn left 90 degrees
-1: turn right 90 degrees
1 <= x <= 9: move forward x units

There are some squares on the grid that are considered obstacles obstacles. The i-th obstacle is located at grid point obstacles[i] = (xi, yi). The robot cannot move onto an obstacle; it will stay on the grid square immediately before the obstacle, but it can still continue attempting the rest of the route. Return the square of the maximum Euclidean distance from the origin to all path points the robot has passed through (with integer coordinates). (That is, if the distance is 5, return 25.)

Note:

North means the +Y direction.
East means the +X direction.
South means the -Y direction.
West means the -X direction.

Solution Approach #

The difficulty of this problem lies in how to use a programming language to describe the robot’s behavior. The following data structures can be used to express the robot’s behavior:

direct:= 0                    // direct indicates the robot's movement direction: 0 1 2 3 4 (north east south west), default facing north
x, y := 0, 0                  // indicates the current robot's horizontal and vertical coordinate position, default is (0,0)
directX := []int{0, 1, 0, -1}
directY := []int{1, 0, -1, 0}
// Combine directX, directY, and direct to indicate that the robot moves in a certain direction
nextX := x + directX[direct]
nextY := y + directY[direct]

The rest of the code can be translated according to the problem statement.

Code #

package leetcode

func robotSim(commands []int, obstacles [][]int) int {
	m := make(map[[2]int]struct{})
	for _, v := range obstacles {
		if len(v) != 0 {
			m[[2]int{v[0], v[1]}] = struct{}{}
		}
	}
	directX := []int{0, 1, 0, -1}
	directY := []int{1, 0, -1, 0}
	direct, x, y := 0, 0, 0
	result := 0
	for _, c := range commands {
		if c == -2 {
			direct = (direct + 3) % 4
			continue
		}
		if c == -1 {
			direct = (direct + 1) % 4
			continue
		}
		for ; c > 0; c-- {
			nextX := x + directX[direct]
			nextY := y + directY[direct]
			if _, ok := m[[2]int{nextX, nextY}]; ok {
				break
			}
			tmpResult := nextX*nextX + nextY*nextY
			if tmpResult > result {
				result = tmpResult
			}
			x = nextX
			y = nextY
		}
	}
	return result
}