A model-based agent in two dimensions, with walls and a map.
What to build
A robot that knows the room's walls but only senses dirt where it stands, visits every reachable square, and cleans what it finds.
Requirements
- Squares:
#wall,.floor,Ddirt,Athe robot's start (clean floor). Each step: on dirt,S(suck). Otherwise mark the square visited; if every square reachable from the start is visited, stop. Otherwise the target is the unvisited reachable square nearest by walking distance (ties: smaller row, then smaller column), and the robot takes the first of the movesU,D,L,Rthat lowers its walking distance to the target by one. - Print the actions as one string of letters (or
none), thenmoves M, cleaned C, score S, where S = 10 × C − M.
Input
Line 1: rows and columns. Then the rows.
Output
Two lines.
Constraints
At most 10 × 10 squares.
Example
Input:
2 3
AD.
..D
Output:
RSRDSLL
moves 5, cleaned 2, score 15
Why it works
Its map lets the robot plan walks around walls, and its memory of visited squares tells it where dirt could still be and when the job is finished.
Examples
2 3 AD. ..D
RSRDSLL moves 5, cleaned 2, score 15
3 3 A#D .#. ...
DDRRUUS moves 6, cleaned 1, score 4
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Compute breadth-first distances over open squares, both from the robot (to pick the target) and from the target (to pick the step).
Hint 2
The robot perceives dirt only in its own square, so it sucks when it stands on dirt and otherwise heads for the nearest square it has not visited.
Solution
Show one correct solution (try it yourself first)
from collections import deque
rows, cols = map(int, input().split())
grid = [list(input()) for _ in range(rows)]
pos = next((r, c) for r in range(rows) for c in range(cols) if grid[r][c] == "A")
MOVES = [("U", -1, 0), ("D", 1, 0), ("L", 0, -1), ("R", 0, 1)]
def distances(source):
dist = {source: 0}
queue = deque([source])
while queue:
r, c = queue.popleft()
for _, dr, dc in MOVES:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] != "#" and (nr, nc) not in dist:
dist[(nr, nc)] = dist[(r, c)] + 1
queue.append((nr, nc))
return dist
reachable = set(distances(pos))
visited, actions, cleaned, moves = set(), [], 0, 0
while True:
r, c = pos
if grid[r][c] == "D":
grid[r][c] = "."
cleaned += 1
actions.append("S")
continue
visited.add(pos)
left = reachable - visited
if not left:
break
here = distances(pos)
target = min(left, key=lambda cell: (here[cell], cell))
to_target = distances(target)
for name, dr, dc in MOVES:
nxt = (r + dr, c + dc)
if to_target.get(nxt) == to_target[pos] - 1:
pos = nxt
moves += 1
actions.append(name)
break
print("".join(actions) or "none")
print(f"moves {moves}, cleaned {cleaned}, score {10 * cleaned - moves}")