THIS TEST
6 5
1 3
6 3
11112
22221
11112
22212
21112
22222

ANS:7 1

I changed my INF to 1e18 and got AC

My old C++ solution got AC with optimized Dijkstra, O(v*log(v)), where v = m*n.
The timing was 0,406 sec.

Evidently, with Python (2.7, 3.4) I got TLE with the same solution. On my machine 500*500 case runs for 4.5 seconds.

Then I realized O(m*n) solution and optimized input as much as possible (Python). It still gives TLE16, on my machine - runs for 2.3 seconds.

Then I run code under PyPy (5.4.1, Python2.7 compatible) and on my machine it runs for 0.383 seconds only. I hope it would AC if PyPy is able to be selected as a programming language.

Please add PyPy!
Thanks

Can anybody that had WA7 give me some hints?
Thanks

Gimme some data, please

But still AC in 0.171s :D
even with super many optimizations (like not reading matrix, thus reading when needed; putting x's and y's in one integer and so on)

come on :D
slower than 2 BFS
and even slower than dijkstra : \\

I suspect that I heavily use deque is the main reason. How can I replace deque with some other decent data structure that will let me quickly add and remove items?

list<> in STL is dumbly slow for little objects ( dafaq who would have thought ?! )

point is equal.
e.g.
3 3
1 1
1 1
111
111
111

answer:1 0

Time limit decreased from 1 second to 0.5 second (it corresponds better to the original TL in 2004). The problem was rejudged. Many old solutions with TLE verdict got AC, while all new solutions working in time from 0.5 to 1 second got TLE.

when trying to update from (ux,uy) to (vx,vy)  i was checking if (vx,vy) was already popped from priority_queue.

this got me wa 22 many times. later, just out of frustation i removed the check and let (vx,vy) be updated even after it was once popped. and u know what, mysteriously got AC. of course, there has to be some logical explanation behind that.

please explain anyone?

Thanks in advance.

run_id = 2970301
test:
10 10
1 1
10 10
1211211212
2111221212
2221001111
1112112012
2112102112
2111200222
1112021212
2222011211
2112222222
2012122122
right_answer: 12 1
my program produces answer 14 1

I spent about an hour till i figured out that:

If it is impossible to get from the computer to the refrigerator, you should output 0 0. !!!!

i got wa on 16 please give me test# 16, i don't know where my mistake: size of heap and arrays are enough.

I've solved this problem in 0.9 sec, just 0.1 sec berofe TL. But I see that there could be much more efficient solution. Please mail me at wooden@bk.ru with a cpp source, it's very interesting for me.

Give me tests please.

Help, me. Pleassse...

.......
Now I AC 0.203s, but 4422 KB

This test help me:
5 7
1 1
3 5
1011111
1211101
1222221
1020101
1111110

5 1

Edited by author 19.04.2006 01:21

Edited by author 19.04.2006 21:02

did anyone make the same mistake?
what's that?

I have written 2 programs and both get WA19
It is very strange, I am already tired to write programs to this problem.

first      2*BFS
secondar   Dijkvasta+Heap
both got Wa19 i not understand why.
Somebody help me?

 ?????????????????????????
 n=3 and m=7
 This is an example test.
 Please admins correct it
 ???????????????????????????



Edited by author 07.10.2005 16:30