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);
}

Download