Thank u so much! How should I forget this!

Maybe that's because you didn't calculate the right shortest-path with the least boots changed(that is, your first number of the output is wrong, but the other one is right). I've got WA7 because I used only one bfs to calculate both values. 2 bfs should be used. (BTW, some of my classmates said only one bfs could also work??? I'm not sure about this.

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.

Example test:

8 8
1 1
8 8
22122111
22121122
22212211
11111222
11122211
22212222
22112121
11122221

Distance table of my TLE21 solution:
0 1 2 4 4 5 6 7
1 1 2 3 4 5 6 7
2 2 2 3 4 5 6 7
3 3 3 3 4 5 6 7
4 4 4 7 6 6 6 7
10 9 8 5 7 7 7 8
10 9 6 6 8 8 8 8
8 7 7 9 9 9 9 9

Distance table of my WA25 solution:
0 1 2 4 4 5 6 7
1 1 2 3 4 5 6 7
2 2 2 3 4 5 6 7
3 3 3 3 4 5 6 7
4 4 4 7 6 6 6 7
10 9 8 7 7 7 7 8
10 9 8 8 8 8 8 8
10 9 9 9 9 9 9 9

Gotta investigate it yet...

see this:
http://acm.timus.ru/status.aspx?space=1&pos=574747

У меня программа тоже находит такой путь.
И я просто к ответу прибавляю всегда 1
Разве путь не :
{
I also find the program that way.
And I just added to the answer is always 1
Is not the way:
}
2 1
3 2
2 3
2 4
1 5
2 6
3 7

А пример:
{Simple}
2 2
1 1
1 2
11
00
My program returns: 2 0
Right ?

Accepted
0.531

Edited by author 03.01.2012 22:24

I followed by your advice, and also suprised!

I get WA 16 too. =)

I don't know your mistake, but my mistake is ... I use "short". Never use "short"! Use "long" or "__int64". =)

Max. count of "boots changes" == 500*500 > 32000. It's funny. =)

o,i see now.

hi
I don't understand in english.
hwo can explain this question in Azeri or Turkish
or in english but with sample sentenceses

I got TL 7 with O(mn) solution...