Page **2** of **2**

### Re: 10496 - Collecting Beepers

Posted: **Sun Dec 21, 2008 8:28 pm**

by **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.

### Re: 10496 - Collecting Beepers

Posted: **Mon Dec 22, 2008 12:37 am**

by **Articuno**

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

### Re: 10496 - Collecting Beepers

Posted: **Wed Oct 27, 2010 4:51 pm**

by **Shafaet_du**

I solved it using recursive backtracking.

### Re: 10496 - Collecting Beepers

Posted: **Fri Apr 04, 2014 6:32 am**

by **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

### Re: 10496 - Collecting Beepers

Posted: **Fri Apr 04, 2014 9:00 pm**

by **brianfry713**

Post your full code.