A warehouse floor is a grid of m rows and n columns, given as a list of m strings of length n. Each character is one cell:
'O': a robot stands here,'E': the cell is empty,'X': a blocker (a shelf, a pillar).
One robot has sent back a sensor reading dist = (up, down, left, right): in each of the four directions, how many steps it would take to walk from its cell onto the nearest blocker in that direction. The area outside the grid counts as a solid wall of blockers, so a robot in row 0 with nothing above it reads up = 1, and a robot in column c with nothing to its left reads left = c + 1. Robots and empty cells don't block the sensor; only 'X' and the outer wall do.
Write find_robots(board: list[str], dist: tuple[int, int, int, int]) -> list[tuple[int, int]] that returns the (row, col) of every robot whose four distances equal dist exactly, in row-major order (by row, then by column). Return [] if no robot matches.
board = [
"OEXO",
"EOEE",
"XEOX",
]
find_robots(board, (1, 2, 1, 2)) # [(0, 0)] up: wall, down: X at (2, 0), left: wall, right: X at (0, 2)
find_robots(board, (2, 2, 2, 3)) # [(1, 1)] up: wall, down: wall, left: wall, right: wall
find_robots(board, (2, 1, 2, 1)) # [(2, 2)] up: X at (0, 2), down: wall, left: X at (2, 0), right: X at (2, 3)
find_robots(board, (1, 2, 1, 1)) # [(0, 3)] down: X at (2, 3), right: wall
find_robots(board, (1, 1, 1, 1)) # []
Constraints: 1 <= m, n, m * n <= 4 * 10**5, and every row has the same length. Any number of cells may be robots.
Scanning outward from every robot costs O(m + n) per robot, which is O(m·n·(m + n)) on a board full of robots. Aim for O(m·n) overall.