## 532 - Dungeon Master

Moderator: Board moderators

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

### 532

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

### Re: 532

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

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

### Re: 532

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

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

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

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

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

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

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!