Poj Solution 2353

http://poj.org/problem?id=2353

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>

#define NMAX 501
#define INF 2000000001
long m[NMAX][NMAX]={0};
long a[NMAX][NMAX]={0};
long M,N;
long b[NMAX*NMAX]={0};
int xp[3]={-1,0,1},yp[3]={0,-1,0};
void solve()
{
    int i,j;
    for(i=1;i<=N;i++)
    {
        m[1][i]=a[1][i];
    }
    for(i=2;i<=M;i++)
    {
        for(j=1;j<=N;j++)
        {
            if(m[i][j]>a[i][j]+m[i-1][j])
                m[i][j]=a[i][j]+m[i-1][j];
        }
        for(j=2;j<=N;j++)
        {
            if(m[i][j]>a[i][j]+m[i][j-1])
                m[i][j]=a[i][j]+m[i][j-1];
        }
        for(j=N-1;j>=1;j--)
        {
            if(m[i][j]>a[i][j]+m[i][j+1])
                m[i][j]=a[i][j]+m[i][j+1];
        }
    }
}
void output()
{
    int kx,ky,i;
    long min=INF;
    int index=1;
    long q=0;
    for(i=1;i<=N;i++)
    {
        if(min>m[M][i])
        {
            min=m[M][i];
            index=i;
        }
    }
    ky=M;
    kx=index;
    b[q++]=kx;
    ky--;
    if(M==1)
    {
        printf("%d",kx);
        return ;
    }
    while(1)
    {
        b[q++]=kx;
        if(ky==1)
            break;
        for(i=0;i<3;i++)
        {
            if(kx+xp[i]<1||kx+xp[i]>N)
                continue;
            if(m[ky][kx]==a[ky][kx]+m[ky+yp[i]][kx+xp[i]])
            {
                ky=ky+yp[i];
                kx=kx+xp[i];
                break;
            }
        }
    }
    for(i=q-1;i>=0;i--)
        printf("%dn",b[i]);
        

}

int main()
{
#if debug     
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    scanf("%d%d",&M,&N);
    int i,j;
    for(i=1;i<=M;i++)
        for(j=1;j<=N;j++)
        {
            scanf("%d",&a[i][j]);
            m[i][j]=INF;
        }
    solve();
    output();
#if debug
    fclose(stdin);
    fclose(stdout);
#endif;
    return 1;
}