You have not ruled out the possibility of infinite loops within the Depth-first search that you build using the queue. I understand that normally you would expect this bug to yield a TLE, however not in this case: your code runs out of memory before it runs out of time.

Adjusting the DFS by adding some safety checks that make sure you don't visit the same cell twice solves the problem: https://codeforces.com/contest/1316/submission/72473517.

Cheers!