10496 - Collecting Beepers

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland

Re: 10496 - Collecting Beepers

Post 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.

Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: 10496 - Collecting Beepers

Post by Articuno »

Thank you mf. I will try to sove it using BFS. Thanks for ur help. :)
May be tomorrow is a better day............ :)

Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh

Re: 10496 - Collecting Beepers

Post by Shafaet_du »

I solved it using recursive backtracking.

New poster
Posts: 20
Joined: Tue May 21, 2013 9:02 pm
Location: BUET

Re: 10496 - Collecting Beepers

Post 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 :D

Thanks Brianfry for his concern :)
Last edited by dhruba07 on Wed Apr 09, 2014 1:55 pm, edited 1 time in total.
Accept who you are :)

Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10496 - Collecting Beepers

Post by brianfry713 »

Post your full code.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 104 (10400-10499)”