3626: 清扫仓库-训练套题T10T2

清扫仓库(clean.pas/c/cpp)

 - 问题描述

李老师的仓库已经有很多年没有清扫了，所以这次的计划是用河水来冲。仓库是一个N*M的矩形，且每个格子里都堆满了尘土。相邻的格子之间都有门，要想让水冲进去，就必须打开这些门。这可不是一件容易的事情。因为有些格子里土堆得很高，因此打开门就很费劲。推开一扇从A格子到B格子的门，需要的力度值为B房间里土堆的高度。写一个程序计算至少需要花费多少力气，才能使所有的格子都进水。

- 输入数据

第一行为N和M(N, M <= 40)，代表仓库的大小。

以后N行，每行N个整数（每个数不超过100），分别表示每个格子里土堆的厚度。

- 输出数据

你得到的结果。所有的格子必须都进水。水是从左上角的格子进去的。

- 样例输入

3 4

3 5 2 1

7 3 4 8

1 6 5 7

- 样例输出

26