拿到這個題，首先這個求最小和非常的簡單，麻煩的是要求出最短路徑。
這個真的是卡了我一陣子。本來紫書上是有解答代碼的，但我想用遞歸去實作，是以一直也就沒看書上的代碼。從網上搜了搜呢，也都是書上的做法，沒有創意。
但好在最終終于是想到了遞歸的實作方式：
首先求和很簡單的dp思想，路徑隻要在求和的基礎上簡單的加一個數組來表示對于這個最一個最小行來說，下一個最小行是多少就行了。直接上代碼會很容易了解：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxr=12;
const int maxc=100+10;
int m,n,p[maxr][maxc],sum[maxr][maxc],w[maxr][maxc];
int main()
{
//freopen("shuJu","w",stdout);
int slove(int,int);
while(scanf("%d%d",&m,&n)!=EOF){
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
scanf("%d",&p[i][j]);
memset(sum,-1,sizeof(sum));
int min_=1<<30,mi;
for(int i=1;i<=m;i++){
int t=slove(i,1);
if(t<min_){
mi=i;
min_=t;
}
}
printf("%d",mi);
mi=w[mi][1];
for(int i=2;i<=n;i++){
printf(" %d",mi);
mi=w[mi][i];
}
printf("\n%d\n",min_);
}
return 0;
}
int slove(int x,int y)
{
if(y==n)
return p[x][y];
if(sum[x][y]!=-1)
return sum[x][y];
int n1=slove(x,y+1),n2=slove(x==1?m:x-1,y+1),n3=slove(x==m?1:x+1,y+1);
sum[x][y]=min(min(n1,n2),n3)+p[x][y];
int a=0x3f3f3f3f;
if(sum[x][y]==n1+p[x][y])
a=x;
if(sum[x][y]==n2+p[x][y])
a=min(a,(x==1?m:x-1));
if(sum[x][y]==n3+p[x][y])
a=min(a,(x==m?1:x+1));
w[x][y]=a;
return sum[x][y];
}