AI: A cleaning robot in a room

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, D dirt, A the 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 moves U, D, L, R that lowers its walking distance to the target by one.
  • Print the actions as one string of letters (or none), then moves 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

Example 1 · Input
2 3
AD.
..D
Expected output
RSRDSLL
moves 5, cleaned 2, score 15
Example 2 · Input
3 3
A#D
.#.
...
Expected output
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}")

Lesson: Intelligent agents →