Vasillia's blog

Why do I get MLE with bfs?
By Vasillia, history, 3 years ago, In English

I don't understand why I get MLE on this problem https://codeforces.me/contest/1955/problem/G when using bfs.

Here is the code: https://codeforces.me/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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Move the line V[pom.first][pom.second] = 1; right before q.push()

→ Reply