Lee algorithm. Runs in O(N * M).

If you don't know it, here is a short description: you start from starting position (sl, sc) and now you expand this node; in a queue you put all its neighbours. You do this only if you optimize by going to that neighbour, i.e. the current cost is shorter than the previous one. let a[i][j] be a matrix with two fields: boots and length. a[i][j] means: minimum number of boots and minimum length to reach (i, j) from start position.
You expand from (x, y) to a neighbour (c, d) when:
a[x][y].boots + 1 (if you change boots, 0 else) < a[c][d].boots or a[x][y].boots + 1 = a[c][d].boots and a[x][y].length + 1 < a[c][d].length. Obvious, you take the valid neighbours (not 0s or outside ones)
hope it's clear...

It could be proved that in Dijkstra's algorithm the choice K = E /V is assimptotically optimal. So, applying to our problem, E / V equals to 8.

I just used the algorithm as you described.
But it got tle.
Anyway thank you very much.
Now I've got it,using heap will help me.

Edited by author 19.04.2004 20:55

I wrote the solution with Lee's algorithm, as it was discribed above by Gheorghe Stefan, and got TL on test 16.
I doubt it works in O(MN).
I test the solution at my local computer - it gaves the correct answers (obviously), but works about 10 times slower, then my solution with Dijkstra!

I BFS on number of boots and Dijkstra on walk-length inside odd/even slices. Dijkstra is linear-time here because of same-length edges (front line is kept as bidirectional list in non-descending order of walk-length, insertion position goes only forwards). AC in 0.062 sec :)

Edited by author 21.08.2008 21:13

Can someone explain where is the problem in this solution?