I used DP from right to left. Any Ideas? Thanx in advance!
Code: Select all
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) {
Main myObj = new Main();
myObj.myMethod();
}
void myMethod() {
String input,cells;
StringTokenizer idata,data;
int r,c,min,min1,last_row;
while((input = Main.ReadLn(255)) != null){
idata = new StringTokenizer(input);
r=Integer.parseInt(idata.nextToken());
c=Integer.parseInt(idata.nextToken());
int [][]Matrix=new int[r][c];
int [][]Minimum=new int[r][c];
for (int i=0;i<r;i++) {
cells=Main.ReadLn(255);
data = new StringTokenizer(cells);
for (int y=0;y<c;y++) {
Matrix[i][y]=Integer.parseInt(data.nextToken());
}
}
for (int i=0;i<r;i++) {
Minimum[i][c-1]=Matrix[i][c-1];
}
for (int j=c-2;j>=0;j--) {
for (int i=0;i<r;i++){
min=Minimum[(i+r-1)%r][j+1];
if (min>Minimum[(i+1)%r][j+1]){
min=Minimum[(i+1)%r][j+1];
}
if (min>Minimum[i][j+1]){min=Minimum[i][j+1];
}
Minimum[i][j]=Matrix[i][j]+min;
}
}
min1=Minimum[0][0];
last_row=0;
for (int i=1; i<r; i++)
if (min1>Minimum[i][0]){ min1 = Minimum[i][0];last_row=i;}
System.out.print(last_row+1);
for (int j=1;j<c;j++) {
int min2=Minimum[(last_row-1+r)%r][j];
int pos=(last_row-1+r)%r;
if (Minimum[last_row][j]<min2){
min2=Minimum[last_row][j];pos=last_row;
}else if (Minimum[last_row][j]==min2 && last_row<pos){
min2=Minimum[last_row][j];pos=last_row;}
if (Minimum[(last_row+1)%r][j]<min2){
min2=Minimum[(last_row+1)%r][j];pos=(last_row+1)%r;
}else if (Minimum[(last_row+1)%r][j]==min2 && (last_row+1)%r<pos){
min2=Minimum[(last_row+1)%r][j]; pos=(last_row+1)%r;}
last_row=pos;
System.out.print(" "+(pos+1));
}
System.out.println();
System.out.println(min1); }
}
static String ReadLn(int maxLg)
{
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";
try {
while (lg < maxLg) {
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
} catch (IOException e) {
return (null);
}
if ((car < 0) && (lg == 0)) return (null);
return (new String(lin, 0, lg));
}
}
).