532 - Dungeon Master

[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]

emma042 cheak this input

Code: Select all

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

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

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

0 0 0

Out should be

Code: Select all

Escaped in 1 minute.

[brianfry713]

Output should be:

Code: Select all

Escaped in 1 minute(s).

[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."

[chanderg_12]

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

[brianfry713]

Dijkstra's algorithm would work the same as BFS with all edges of weight 1. It is less efficient though.

[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]

yes

[walking_hell]

thanx for the reply brianfry...i got it accepted...i misunderstood the problem..

[brianfry713]

I just ran a single BFS from the start to the exit. What are you trying to do?