yobro97
yobro97

Reputation: 1145

Maze Solving From All Start Points

Recently I came across a problem that stated;
Assume a maze having characters *,.,C .* represents walls and ./C are allowed. There is only one point which is marked C. Now given a bot stands on any of the allowed points, there exists a series of commands (for example LDDRU or LLLRRDU,etc.) such that if the bot starts from any allowed point, it passes through C at least once.
Eg:

******
*.C..*
**.***
*....*
******

Command: RLLURUU

Now I know how to solve a maze using DFS/BFS(for shortest path). But can anyone provide a hint on how I shall proceed problems like this?
EDIT: if the next move is into walls / outside maze, it is ignored. And as usual L IS LEFT R IS RIGHT U IS UP D IS DOWN.

Upvotes: 2

Views: 562

Answers (1)

templatetypedef
templatetypedef

Reputation: 372704

This problem is related to the concept of synchronizing words or reset sequences for finite automata. You can imagine building an automaton where

  1. each open space, plus C, is a state;
  2. each state other than C transitions to itself for every move that hits a wall;
  3. each state other than C transitions to a neighboring open state in the indicated direction if there's an open spot in that direction; and
  4. the C state transitions to itself on all moves.

Given this automaton, you're now looking for a sequence that takes every state to the C state, hence the connection to synchronizing words. There are a number of algorithms for finding synchronizing words, and any of them could be adapted to solve this particular problem. One option would be to build the power automaton from the original automaton and to look for a path from the start state to the C state, which (I believe) ends up being a theoretically optimal version of the comment talking about collapsing virtual robots together (in that it will always find the optimal path.)

Upvotes: 2

Related Questions