TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P6305
  • 問題
  • P6305飞越原野
    制限 : 時間制限 : - MS   メモリ制限 : - KB
    審判説明 : 3s 256MB
    問題説明

    在一片广阔的土地上,有一个鸟人,他需要从这里穿过原野,回到基地。这片原野上,有平地(P)、有湖泊(L),因为鸟人可以飞,所以呢,有的时候,他可以飞越湖泊。现在,鸟人需要用最快的时间,回到基地。 假设原野是一个m*n的矩阵,有两种地形,用P和L表示。鸟人只能停留在平地上。他目前处在(1,1)这个位置,而目的地是(m,n)。他可以向上下左右四个方向移动,或者飞行。每移动一格需要1个单位时间。而飞行无论飞多远,都只需要1个单位时间。飞行的途中不可以变方向,也就是说飞行也只能是上下左右四个方向。并且一次飞行最终必须降落在平地上。当然,受到能量的限制,鸟人不能无限制的飞行,他总共最多可以飞行的距离为D。

    入力形式

    第一行是三个整数,m,n,D,三个数都不超过100,下面是一个m*n的矩阵,表示原野

    出力形式

    一个整数,为最短时间,如果无法到达,则输出“impossible”

    サンプル入力

    4 4 2
    PLLP
    PPLP
    PPPP
    PLLP

    サンプル出力

    5