• [B] Escape

  • 时间限制: 1000 ms 内存限制: 65535 K
  • 问题描述
  • Unfortunately you are trapped in an n × m matrix, each grid either is “.” denoting ground

    which you can stay, or is “#”denoting trap which you can not stay.

    On the other hand, you only left t seconds, so you want to leave this matrix as soon as
    possible and you must know every seconds you can move to the adjacent grids(left, right, up and
    down), firstly you position is (1, 1) and your destination is (n, m).
  • 输入
  • Input starts with an integer T( T ≤100 )denoting the number of test case.
    For each test case, first line will contain n and m ( 1≤n , m≤20 ) and t( t≤100 )
    then n lines followed, each line contains m characters.
  • 输出
  • For each test case, print the case number and your answer, if it is impossible to get to the
    destination, output “Impossible”, otherwise output the minimum time you need to get to the
    destination.
  • 样例输入
  • 2
    3 3 5
    .##
    ...
    ##.
    3 3 3
    .##
    ...
    ##.
  • 样例输出
  • Case 1: 4
    Case 2: Impossible
  • 提示
  • In the first sample, you can along  (2, 1), (2, 2), (2, 3) from (1, 1) to (3, 3)
  • 来源
  • Alex@NBUT
  • 操作

显示春菜