P1541 - 【提高】小 X 学游泳(swim)

内存限制：128 MB 时间限制：1.000 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：7 通过：2

提交提交记录统计

暑假快到啦，小 X 准备趁着这个暑假去学游泳。可是一开始小 X 就遇到了一个难题。

游泳池划分成了一个 n×m 的方格，这里 n×m 表示 n 行 m 列。因为游泳池里的水深浅不一，所以这n×m 个方格对于小 X 的危险系数也会不一样。

而小 X 目前需要从左上角的方格（ 1， 1）出发，游到右下角的方格（ n， m），小 X 每次只能从当前方格游到上下左右四个相邻的方格中的某一格，并且在到达终点前不能离开游泳池。

小 X 很担心会发生什么危险，所以希望你能帮他找一条危险系数最小的路径。

一条路径的危险系数定义为这条路径所经过的方格的危险系数之和。

注意：这条路径不能经过同一个方格两次（小 X 当然不希望去那么危险的地方再游一次）

输入数据第一行有两个用空格隔开的正整数 n 和 m，表示泳池的行数和列数。

接下来共有 n 行数据，每行有 m 个用空格隔开的大于等于 0 的整数，表示每个方格的危险系数

输出仅有一行包含一个整数ans，表示要求的从左上角的方格（ 1， 1）出发，游到右下角的方格（ n， m）的最小的危险系数。

【数据范围】

对于 30% 的数据， 1 ≤ n， m ≤ 5

对于另外 40% 的数据， 1 ≤ n， m ≤ 20 ，每个方格的危险系数 = 0 或 1

对于 100% 的数据， 1 ≤ n， m ≤ 30， 0 ≤ 每个方格的危险系数 ≤ 100000

【样例解释】

路径：（ 1， 1） →（ 1， 2） →（ 1， 3） →（ 2， 3） →（ 2， 4） →（ 2， 5） →（ 3， 5） →（ 4， 5），

危险系数之和为 1+7+2+1+5+1+1+1=19。

来源
常州市2016“信息与未来”夏令营选拔赛

建议

请使用深搜和广搜分别实现

1541: 【提高】小 X 学游泳(swim)