I don't understand why I get MLE on this problem https://mirror.codeforces.com/contest/1955/problem/G when using bfs.
Here is the code: https://mirror.codeforces.com/contest/1955/submission/255789320.
I was able to solve it later with dfs, but I'm still confused why this bfs that i wrote does not work. Obviously the problem is in this queue Q, but after every bfs call it should be empty again, so size of Q is always <= 100 * 100, which should not get out of memory limit. I would appreciate if someone will help me understand this.
in your code's bfs, you did not check if the cell is already visited or not, so it checks the same cell multiple times instead of just once, which made the memory (and also time) exploded as the queue could have like around $$$O(n^2m^2)$$$ elements at some point.
Hmm, I thought I did check that. In this array V, V[x][y] is 1 if i visited that node. And before I push node to queue I check if V of that node is 0.
well, if your idea to check if visited is like that, then i suggest you to just assign $$$V[x][y] = 1$$$ as soon as you push $$${x,y}$$$ to the queue $$$Q$$$ instead (to avoid pushing the same nodes into the queue multiple times).
Move the line
V[pom.first][pom.second] = 1;right beforeq.push()yeah exactly. I used to make this mistake a lot :)
Ahh, okay I understand it now. Thank you.