532 - Dungeon Master

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

Moderator: Board moderators

live_lie
New poster
Posts: 19
Joined: Mon Nov 29, 2010 11:50 pm

532

Post by live_lie » Thu May 26, 2011 11:07 pm

can anyone please help me to understand this problem.. actually how i need to thing or how i use bfs here...what are the vetices or edges....?

shuvokr
Learning poster
Posts: 66
Joined: Tue Oct 02, 2012 8:16 pm
Location: Bangladesh

Re: 532

Post by shuvokr » Wed Jul 24, 2013 3:10 pm

emma042 cheak this input

Code: Select all

3 4 5
SE...
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
#####

0 0 0
Out should be

Code: Select all

Escaped in 1 minute.

Code: Select all

enjoying life ..... 

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

Re: 532

Post by brianfry713 » Wed Jul 24, 2013 10:54 pm

Output should be:

Code: Select all

Escaped in 1 minute(s).
Check input and AC output for thousands of problems on uDebug!

shuvokr
Learning poster
Posts: 66
Joined: Tue Oct 02, 2012 8:16 pm
Location: Bangladesh

Re: 532

Post by shuvokr » Thu Jul 25, 2013 12:12 am

May be for this problem there is no input which result is "Escaped in 1 minute(s)." because my ac code for result 1 print "Escaped in 1 minute."

Code: Select all

enjoying life ..... 

chanderg_12
New poster
Posts: 5
Joined: Fri Nov 15, 2013 2:06 pm

Re: 532

Post by chanderg_12 » Fri Nov 15, 2013 3:06 pm

Why not use Dijkistra?Though all edges are basically 1 or INF , still it should do the trick right?

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

Re: 532

Post by brianfry713 » Fri Nov 15, 2013 9:20 pm

Dijkstra's algorithm would work the same as BFS with all edges of weight 1. It is less efficient though.
Check input and AC output for thousands of problems on uDebug!

chanderg_12
New poster
Posts: 5
Joined: Fri Nov 15, 2013 2:06 pm

Re: 532

Post by chanderg_12 » Wed Nov 20, 2013 6:05 pm

Thanks. Ya, I get it.I saw paths and was naively led to Dijkstra's.
And this works only because of constant edge length right? As we cover all vertices of each depth before going farther from the source, we end up with the optimal path.

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

Re: 532

Post by brianfry713 » Wed Nov 20, 2013 10:03 pm

yes
Check input and AC output for thousands of problems on uDebug!

walking_hell
New poster
Posts: 14
Joined: Tue Sep 24, 2013 4:35 pm

uva 532

Post by walking_hell » Sun Nov 24, 2013 12:59 am

thanx for the reply brianfry...i got it accepted...i misunderstood the problem..
Last edited by walking_hell on Mon Nov 25, 2013 11:55 pm, edited 1 time in total.

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

Re: uva 532

Post by brianfry713 » Mon Nov 25, 2013 11:47 pm

I just ran a single BFS from the start to the exit. What are you trying to do?
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 5 (500-599)”