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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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