Vasillia's blog

Why do I get MLE with bfs?
By Vasillia, history, 8 months ago, In English

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.

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

»
8 months ago, # |
  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
  • »
    »
    8 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      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).

      → Reply
»
8 months ago, # |
  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
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yeah exactly. I used to make this mistake a lot :)

    → Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Ahh, okay I understand it now. Thank you.

    → Reply