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;
}
```
This entry was posted in poj. Bookmark the permalink.