program ti1029;
var
  f:array[0..501,0..501]of integer;
  w,dp:array[0..501,0..501]of extended;
  i,j,k,n,m:integer;

procedure print(x,y:integer);
  begin
    if x<>1
      then begin
             if f[x,y]=y
               then print(x-1,y)
               else print(x,f[x,y]);
           end;
    writeln(y);
  end;

begin
  readln(m,n);
  for i:=1 to m do
   for j:=1 to n do
     read(w[i,j]);
  fillchar(dp,sizeof(dp),0);
  fillchar(f,sizeof(f),0);
  for i:=1 to n do
    dp[1][i]:=w[1][i];
  for i:=2 to m do
    begin
      for j:=1 to n do
        begin
          dp[i][j]:=dp[i-1][j]+w[i][j];
          f[i][j]:=j;
        end;
      for j:=2 to n do
        if dp[i][j-1]+w[i][j]<dp[i][j]
          then begin
                 dp[i][j]:=dp[i][j-1]+w[i][j];
                 f[i][j]:=j-1;
               end;
      for j:=n-1 downto 1 do
        if dp[i][j+1]+w[i][j]<dp[i][j]
          then begin
                 dp[i][j]:=dp[i][j+1]+w[i][j];
                 f[i][j]:=j+1;
               end;
    end;
  j:=1;
  for i:=1 to n do
    if dp[m][i]<dp[m][j]
      then j:=i;
  print(m,j);
end.

try

5 6
525   0 171   0 872 673
  0 843   0   0   0   0
  0 277   0 202   0   0
  0   0 733 957  65  96
637 566   0   0   0 441

answer:
4 4 5 5 5 5

some tests
input
3 4
0 0 0 0
0 0 0 0
0 0 0 0
output
1 1 1(or some like that)

input
3 4
1 0 0 0
1 0 0 0
0 1 1 2
output
2 2 1 1(or some like that)

Edited by author 20.03.2009 11:32

Is 4 4 5 5 5 5 4 3 correct?

The fee is a "positive" integer not exceeding 10^9.