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

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

Re: 10496 - Collecting Beepers

Post by mf » Sun Dec 21, 2008 8:28 pm

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
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: 10496 - Collecting Beepers

Post by Articuno » Mon Dec 22, 2008 12:37 am

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

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

Re: 10496 - Collecting Beepers

Post by Shafaet_du » Wed Oct 27, 2010 4:51 pm

I solved it using recursive backtracking.

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

Re: 10496 - Collecting Beepers

Post by dhruba07 » Fri Apr 04, 2014 6:32 am

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 :)

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

Re: 10496 - Collecting Beepers

Post by brianfry713 » Fri Apr 04, 2014 9:00 pm

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

Post Reply

Return to “Volume 104 (10400-10499)”