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 ?! )