Labyrinth P79535


Statement
 

pdf   zip

html

You are given an R × C grid. Some cells, marked with ‘#’, have a wall. The rest of cells are free, and they are marked with ‘.’. There are two exceptions: one free cell is marked with ‘S’ (it is your starting position), and another free cell is marked with ‘T’ (it has a treasure).

Your goal is to reach the treasure as fast as possible. Every second, you can either move to an adjancent free cell, or hit an adjancent wall with a hammer. You know that every wall vanishes after H hits.

Input

Input consists of several cases, each with R, C and H, followed by R lines with C characters each. Assume that R and C are between 1 and 1000, and that H is between 1 and 105.

Output

For every case, print the minimum time to reach the treasure from the starting position.

Public test cases
  • Input

    1 2 20
    ST
    
    2 3 10
    S..
    ..T
    
    2 3 10
    S##
    ##T
    
    3 3 10
    T..
    ##.
    S..
    
    3 3 3
    T..
    ##.
    S..
    
    4 6 100000
    T##S#.
    ..###.
    ...#..
    ......
    

    Output

    1
    3
    23
    6
    5
    100013
    
  • Information
    Author
    Pol Mauri
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Quinzè Concurs de Programació de la UPC - Semifinal
    Date
    2017-06-29