TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P3189
  • 問題
  • P3189逃离迷宫3
    制限 : 時間制限 : 10000 MS   メモリ制限 : 65536 KB
    問題説明

    有一个方格迷宫,我们可以将它看作一个n*m的矩阵,每个方格表示一个房间,每个方格中都有数字。数字-1表示该房间内有陷阱,不能通过。如果格子里是>=0的数字,表示该房间中有怪兽,数字代表该怪兽的杀伤力,何老板通过该房将会失去对应数值的生命值。

    一开始何老板位于左上角的方格(坐标[1,1]位置),他要走到右下角的出口(坐标[n,m]位置),每一步何老板可以往上、下、左、右走。 他想知道最少需要失去多少生命值就可以走出迷宫?

    入力形式

    第一行,两个整数n和m
    接下来是一个由整数构成的n*m的矩阵,表示迷宫

    出力形式

    一个整数,表示最失去的生命值。若无解,输出-1

    サンプル入力

    4 6
    20 100 50 -1 -1 10
    10 -1 50 10 10 5
    10 -1 70 -1 10 -1
    20 30 20 50 20 10

    サンプル出力

    190

    ヒント

    1<=n,m<=30
    -1<=矩阵中的数字<=500