10496 - Collecting Beepers

[mf]

Greedy shouldn't work here.

BFS can work, with a special graph, of course - each state should be a triple (x, y, m), where m is a bitmask, representing the subset of collected beepers.

[Articuno]

Thank you mf. I will try to sove it using BFS. Thanks for ur help.

[Shafaet_du]

I solved it using recursive backtracking.

[dhruba07]

This problem can be solved by recursive backtracking.

The only thing to look at is :http://en.wiktionary.org/wiki/Manhattan_distance

Because this grid has no obstacles in path, so the distance can be directly calculated by Manhattan Distance.

So choose one beeper,backtrack and then choose another


Thanks Brianfry for his concern

[brianfry713]

Post your full code.