Reputation: 1145
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
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
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