HAF1 - Đua Xe
Tác giả: ll931110
Ngôn ngữ: C++
#include <iostream>
#define MAXN 1001
using namespace std;
int a[MAXN][MAXN], f[MAXN][MAXN];
int main()
{
int i,j,m,n,res;
//freopen("haf1.inp","r",stdin);
//freopen("haf1.out","w",stdout);
scanf("%d%d", &n, &m);
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++)
scanf("%d",&a[i][j]);
for (i = 1; i <= n; i++)
f[1][i] = a[1][i];
for (i = 2; i <= m; i++)
{
for (j = 1; j <= n; j++)
f[i][j] = f[i - 1][j] + a[i][j];
for (j = 2; j <= n; j++)
if (f[i][j] > f[i][j - 1] + a[i][j])
f[i][j] = f[i][j - 1] + a[i][j];
for (j = n - 1; j > 0; j--)
if (f[i][j] > f[i][j + 1] + a[i][j])
f[i][j] = f[i][j + 1] + a[i][j];
}
res = MAXN * MAXN;
for (i = 1; i <= n; i++)
if (res > f[m][i]) res = f[m][i];
printf("%d",res);
}