xfstart07
Get busy living or get busy dying

#include < iostream >
using   namespace  std;

int  N,M;
int  g[ 110 ][ 510 ] = { 0 };
long   long  f[ 110 ][ 510 ] = { 0 };
int  p[ 110 ][ 510 ] = { 0 };
int  l = 0 ,path[ 5100 ];
int  main()
{
    scanf(
" %d%d " , & N, & M);
    
for ( int  i = 1 ;i <= N; ++ i)
        
for ( int  j = 1 ;j <= M; ++ j)
            scanf(
" %d " , & g[i][j]);
    
for ( int  i = 1 ;i <= M; ++ i)
        f[
1 ][i] = g[ 1 ][i];
    
for ( int  i = 2 ;i <= N; ++ i){
        
for ( int  j = 1 ;j <= M; ++ j){
            f[i][j]
= f[i - 1 ][j] + g[i][j];
            p[i][j]
=- 2 ;
        }
        
for ( int  j = 2 ;j <= M; ++ j)
            
if (f[i][j] > f[i][j - 1 ] + g[i][j]){
                f[i][j]
= f[i][j - 1 ] + g[i][j];
                p[i][j]
=- 1 ;
            }
        
for ( int  j = M - 1 ;j >= 1 ; -- j)
            
if (f[i][j] > f[i][j + 1 ] + g[i][j]){
                f[i][j]
= f[i][j + 1 ] + g[i][j];
                p[i][j]
= 1 ;
            }
    }
    
int  x,y = 1 ;
    
for ( int  i = 2 ;i <= M; ++ i)
        
if (f[N][i] < f[N][y])
            y
= i;
    x
= N;
    
while (x != 1 ){
        l
++ ; path[l] = y;
        
if (p[x][y] ==- 2 )
            x
-- ;
        
else
            y
+= p[x][y];
    }
    l
++ ; path[l] = y;
    
for ( int  i = l;i >= 1 ; -- i)
        printf(
" %d\n " ,path[i]);
    
return   0 ;
}


posted on 2009-05-31 20:32 xfstart07 阅读(153) 评论(0)  编辑 收藏 引用 所属分类: 代码库

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理