Code: Select all
#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
#define max pow(2,30)
using namespace std;
long long int dp[20][121];
long long int save[20][121];
long long int trace[20][121];
long long int track[20][121];
vector<long long int>v;
long long int r,c;
long long int rec(long long int row,long long int colum){
if(colum==c-1)return save[row][colum];
else{
if(dp[row][colum]!=max)return dp[row][colum];
else{
long long int j,k;
long long int i=save[row][colum]+rec(row,colum+1);
if(row==0){
j=save[row][colum]+rec(r-1,colum+1);
k=save[row][colum]+rec(row+1,colum+1);
}
else if(row==r-1){
j=save[row][colum]+rec(row-1,colum+1);
k=save[row][colum]+rec(0,colum+1);
}
else{
j=save[row][colum]+rec(row-1,colum+1);
k=save[row][colum]+rec(row+1,colum+1);
}
if(i<j && i<k){
trace[row][colum]=1;
return dp[row][colum]=i;
}
else if(j<i&& j<k ){
trace[row][colum]=2;
return dp[row][colum]=j;
}
else if(k<j && k<i){
trace[row][colum]=3;
return dp[row][colum]=k;
}
else if(i==j && j<k){
if(row==0){
trace[row][colum]=1;
return dp[row][colum]=i;
}
else{
trace[row][colum]=2;
return dp[row][colum]=j;
}
}
else if(j==k && j<i){
if(row==0){
trace[row][colum]=3;
return dp[row][colum]=k;
}
else if(row==r-1){
trace[row][colum]=3;
return dp[row][colum]=k;
}
else{
trace[row][colum]=2;
return dp[row][colum]=j;
}
}
else if(i==k && i<j){
if(row==r-1){
trace[row][colum]=3;
return dp[row][colum]=k;
}
else{
trace[row][colum]=1;
return dp[row][colum]=i;
}
}
else if(i==j && i==k){
if(row==0){
trace[row][colum]=1;
return dp[row][colum]=i;
}
else if(row==r-1){
trace[row][colum]=3;
return dp[row][colum]=k;
}
else{
trace[row][colum]=2;
return dp[row][colum]=j;
}
}
}
}
}
void copy(long long int a[20][121],long long int b[20][121]){
int i,j,k;
for(i=0;i<r;i++){
for(j=0;j<c;j++){
a[j]=b[j];
}
}
}
void insert(long long int a,long long int b){
if(b!=c-1){
if(track[a]==1){
v.push_back(a);
insert(a,b+1);
}
else if(track[a]==2){
if(a==0){
v.push_back(r-1);
insert(r-1,b+1);
}
else {
v.push_back(a-1);
insert(a-1,b+1);
}
}
else if(track[a]==3){
if(a==r-1){
v.push_back(0);
insert(0,b+1);
}
else{
v.push_back(a+1);
insert(a+1,b+1);
}
}
}
}
int main(){
long long int a,b,d,e,f,n,T;
while(cin>>r>>c){
v.clear();
for(a=0;a<20;a++){
for(b=0;b<121;b++){
save[a]=0;
trace[a]=0;
dp[a]=max;
}
}
for(a=0;a<r;a++){
for(b=0;b<c;b++){
cin>>save[a];
}
}
long long int min=max;
long long int strt;
for(a=r-1;a>-1;a--){
long long int i=rec(a,0);
if(i<=min){
memset(track,0,sizeof(track));
min=i;
copy(track,trace);
strt=a;
}
}
v.push_back(strt);
insert(strt,0);
for(a=0;a<v.size();a++){
if(a!=v.size()-1){
cout<<v[a]+1<<" ";
}
else{
cout<<v[a]+1<<endl;
}
}
cout<<min<<endl;
}
return 0;
}