这题是一道dp的水题，类似于数塔，从右向左倒着加上去，找到最小值，然后在从左到右输出路径。
#include"iostream"
#include"stdio.h"
#include"algorithm"
#include"string.h"
#include"string"
#include"cmath"
#include"queue"
#include"stack"
#include"map"
using namespace std;
const int mx=;
const int inf=;
int n,m;
int maze[mx][mx];
int MIN(int a,int b,int c)
{
int d=a<b?a:b;
return c<d?c:d;
}
void DP()
{
int i,j;
for(j=m-;j>=;j--)
{
for(i=;i<n;i++)
{
maze[i][j-]+=MIN(maze[(i+n-)%n][j],maze[i][j],maze[(i+)%n][j]);
}
}
}
void OUTPUT()
{
int i,j,min_length=inf,path;
for(i=;i<n;i++)
{
if(maze[i][]<min_length)
{
min_length=maze[i][];
path=i;
}
}
cout<<path+;
for(j=;j<m;j++)
{
int r=path;
int min_num=maze[path][j];
if(maze[(path+n-)%n][j]==min_num)
{
if((path+n-)%n<r) r=(path+n-)%n;
}
else if(maze[(path+n-)%n][j]<min_num)
{
min_num=maze[(path+n-)%n][j];
r=(path+n-)%n;
} if(maze[(path+)%n][j]==min_num)
{
if((path+)%n<r) r=(path+)%n;
}
else if(maze[(path+)%n][j]<min_num)
{
r=(path+)%n;
min_num=maze[(path+)%n][j];
}
path=r;
cout<<" "<<path+;
}
cout<<endl<<min_length<<endl;
}
int main()
{
// freopen("E:\\in.txt","r",stdin);
int i,j;
while(scanf("%d%d",&n,&m)==)
{
for(i=;i<n;i++)
{
for(j=;j<m;j++)
{
scanf("%d",&maze[i][j]);
}
}
DP();
OUTPUT();
}
return ;
}