Are you local mins such that all neighbours are strictly superior ? (probably not, since it would only find isolated mins)
Then, when you do your BFS, are you looping over all the local minimas ? Are you not doing some redundancy here ?
I mean, once a square has been connected to a minima, I never look at it again.
I think in total, my program runs with O(n log n) for the sort (I think that's worst case of python sort), and then O(4*n)
(each square can be looked at for all of his four neighbours, and I'm not even sure that's possible. But maybe my calculation is wrong and it's higher than that...
I'm really annoyed by not being able to know why we fail (as in wrong answer / delay) as it would help the debugging