0
$\begingroup$

The question is:

There is a n x n grid (Maze) which has either 0, 1 or 2. 0 means a path exists, 1 means the cell is blocked and 2 means there exists gold in that cell. Task is to start from 0, 0 and cover the grid such that all the gold is collected and then returned to a specific cell (x, y) in the grid. This task has to be done in the minimum number of steps.

Example:
Input: Maze = {0, 2, 0}, {0, 0, 1}, {1, 1, 1} and x = 1, y = 1 (return to this cell)

Output: 1 as there is only 1 gold (in 1,1) and we are to return also in (1,1) so 1 move is what we need.

Reading the question, I can speculate that this is perhaps a variant of the traveling salesman problem but I cannot think of how I should be applying it here. Also, since in Travelling Salesman we return back to the source node and here we do not, I am having second thoughts if this has TSP like implementation. Any ideas?

$\endgroup$
1
$\begingroup$

Travelling Sales Man is NP-complete. This problem isn't, it has an easy polynomial time solution. Don't go there.

$\endgroup$
  • $\begingroup$ What is a polynomial time solution for this problem? $\endgroup$ – user248884 Nov 1 '18 at 8:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.