225. Find Robots in Location Map by Nearest Blockers

Find Robots in Location Map by Nearest Blockers

You are given a robot location map and a query describing required distances from a robot to the nearest blocker. Find all robots whose nearest blocker distances exactly match the query.

Only X cells and map boundaries are blockers. Other robots do not block movement.

The map contains three types of cells:

O: robot
E: empty cell
X: blocker

The query contains four integers in this order: [left, top, bottom, right].

The map boundary is treated as a blocker just outside the grid. If a robot moves past the first row, last row, first column, or last column, it reaches the boundary blocker. Therefore, a robot on the top row has top distance 1, and a robot in the leftmost column has left distance 1.

Method Signature

List<String> findRobots(List<String> locationMap, List<Integer> query)

Parameters

locationMap: a list of strings representing the grid.
query: a list of exactly four integers in the order [left, top, bottom, right].

Returns

Return a list of robot coordinates that satisfy the query.
Each coordinate must be returned as a string in the format "row,col".
Rows and columns are zero-indexed.
The output must be sorted by smaller row first. If rows are equal, sort by smaller column first.
If no robot satisfies the query, return an empty list.

Constraints

1 ≤ locationMap.size() ≤ 1,000
1 ≤ locationMap[i].length() ≤ 1,000
All rows in locationMap have the same length.
locationMap[i][j] is one of 'O', 'E', or 'X'.
query.size() = 4
1 ≤ query[i] ≤ 1,000
The total number of cells is at most 1,000,000.

Examples

Example 1

findRobots(locationMap = List.of("OEEX", "EEEX", "XEOE", "EEEE"), query = List.of(2, 3, 2, 2))

Output:

List.of("2,2")

Explanation: The robot at coordinate "2,2" has nearest blocker distances left = 2, top = 3, bottom = 2, and right = 2.

Example 2

findRobots(locationMap = List.of("EOE", "EEE", "EOE"), query = List.of(2, 1, 3, 2))

Output:

List.of("0,1")

Explanation: There are two robots, but only the robot at "0,1" matches all four required distances.

Example 3

findRobots(locationMap = List.of("OXO", "EEE", "OXO"), query = List.of(1, 1, 3, 1))

Output:

List.of("0,0", "0,2")

Explanation: The robots at "0,0" and "0,2" match the query. The robots in the last row do not match because their top and bottom distances are different.

Example 4

findRobots(locationMap = List.of("OEX", "EEE", "XEO"), query = List.of(3, 3, 1, 1))

Output:

List.of()

Explanation: No robot has the exact required nearest blocker distances.