Queue Overflow in BFS

Правка en1, от stark_arya, 2018-12-20 15:20:34

I am trying to solve this question 884E. Here we are given a simple 0-1 grid of max size (2^12 * 2^14). We need to determine the number of connected components consisting of 1's. The memory limit is 16 MB.

To solve this, I am using bfs with a circular queue of fixed size around 1.5e6. The whole thing (queue + grid) fits into the memory limit.

For every non-visited 1, I am starting a bfs to cover all 1's in its component. The maximum number of cells in the queue at a time should be O(n+m). The problem is my queue is overflowing in one of the cases for no reason I see.

Is there something wrong with the logic or with the implementation? My code

Теги #bfsgrid, circulararray, queue, overflow

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский stark_arya 2018-12-20 15:20:34 798 Initial revision (published)