Description
cloverprince养着一只小马，活泼可爱，很喜欢在外面玩。有一天，小马驮着一袋盐从一条小河上经过，到了河对岸，他发现，身上的盐轻了不少，好像自己的力气变大了似的。从此，小马开始喜欢过河。每天都要经过小河，到河对岸的草地上去玩。
有一天，小马玩得很开心，不知不觉，天色已经晚了。小马想起了王子要他晚上早点回家，否则王子会生气的。于是，小马想用最快的速度过河。
河水有缓有急，不同地方深浅也不一样，因此，在河的不同地方，行走的速度是有区别的。小马把河划分成N*M个矩形区域，像一个矩阵，南北N个区，东西M个区。小马现在在河的南岸，要走到北岸去。小马可以从任何邻接南岸的区域进入河中；在河里，每次只能从当前区域走到北方、东北、西北三个相邻区域；只要走到最北边的任何一个区域，下一步就可以上岸。小马在每个区域中需要停留的时间不尽相同。 请你帮助小马计算一下它在河里至少需要停留多长时间才能过河。
Input
包含多个测试用例，不超过5个，连续给出
每个测试用例中：
第一行是两个正整数N,M，表示区域的个数。
第2至第N+1行，每行M个正整数，是一个N行M列矩阵。每个元素表示如果进入这个区域，需要逗留的时间。
区域给出的顺序：逐行由北向南，每行由西向东。
接着是下一个测试用例。
读到N=M=0时结束。
数据限制：
0 < N,M <= 1000
矩阵中每个元素不超过1000之间。
Output
对于每个测试用例，输出一行，仅包含一个整数，就是过河需要的最短时间。
Sample Input
5 5
1 2 3 4 5
2 2 3 3 4
5 4 1 2 8
9 2 3 6 3
1 1 6 2 2
0 0
Sample Output
7
Hint
顺次经过第5行第1列、第4行第2列、第3行第3列、第2行第2列、第1行第1列，在河里停留的时间总共是1+2+1+2+1=7。
矩阵从第一行到第N行表示由北向南，求小马从南岸到北岸的最短时间，可以使用动态规划来求解，从北向南计算小马走到每一行总最短逗留时间。初始状态即最北岸一行的最短逗留时间，第i+1行的最短逗留时间就是该区域停留时间，加上从该区域东北、北方、西北三个方向逗留时间中的最小值。最后得到第N行的最小值，就是小马从南到北过河的最少停留时间。
状态转移方程为：
dp[i][j] = min( dp[i-1][j-1] , dp[i-1][j] , dp[i-1][j+1]) + s[i][j];
需要注意的是单行多列的情况。
#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <vector>
#include <list>
#include <math.h>
#include <algorithm>
using namespace std;
int s[1001][1001],dp[1001][1001];
int min2(int a,int b)
{
if(a<b)
return a;
else return b;
}
int min3(int a,int b,int c)
{
if(a<b)
{
if(a<c)return a;
else return c;
}
else
{
if(b<c)return b;
else return c;
}
}
int main()
{
int n, m , time;
while(scanf("%d %d",&n,&m) && n!=0 && m!=0)
{
if( n == 0 && m==0 )break;
int i,j;
for( i = 0 ; i < n ; i++ )
for( j = 0 ; j < m ; j++)
scanf("%d",&s[i][j]);
for( j = 0 ; j < m ; j++ )
dp[0][j] = s[0][j];
for( i = 1 ; i < n ; i++ )
{
if( m > 1 )
{
dp[i][0] = min2( dp[i-1][0] , dp[i-1][1] ) + s[i][0];
dp[i][m-1] = min2( dp[i-1][m-2] , dp[i-1][m-1] ) + s[i][m-1];
for( j = 1 ; j < (m-1) ; j++ )
dp[i][j] = min3( dp[i-1][j-1] , dp[i-1][j] , dp[i-1][j+1]) + s[i][j];
}
else
{
dp[i][0] = dp[i-1][0] + s[i][0];
}
}
time = 9999999;
for( j = 0 ; j < m ; j++ )
if( dp[n-1][j] < time ) time = dp[n-1][j];
printf("%d\n",time);
}
return 1;
}