Question on 27.1 Batch Processing: how to calculate minimum distance to a black square for all white squares in one BFS?

[chao1995]

Hi @pllk, I really appreciate your huge efforts for writing this book and making it free and available. Thank you so much!

I have a question when I am reading 27.1 Batch Processing. The problem statement (not the latest version) is

Given a grid of size k by k initially consists of white squares and our task is to perform n operations, each of which is one of the following:

• paint square (y,x) black

• find the nearest black square to square (y,x) where the distance between
  squares (y1,x1) and (y2,x2) is |y1 - y2| + |x1 - x2|

There is a pre-processing step in each batch, to calculate for each square of the grid the smallest distance to a black square. This can be done in O(k^2) time using breadth-first search.

My question is: how is calculating for each square of the grid the smallest distance to a black square done in one BFS? (I can't figure out which square to start the BFS.)

Thanks in advance!

Btw, which is the better place, codeforces or this repo, to post questions when reading the book?

[pllk]

Thank you! The trick is to start the search at each black square simultaneously. You can first add all black squares to the queue with distance 0, and then perform the search as usual.

Questions can be posted either here or on Codeforces. "Issues" are things that should be fixed, and usually questions point out such things because the book should be easy to understand.

[chao1995]

The trick is to start the search at each black square simultaneously. You can first add all black squares to the queue with distance 0, and then perform the search as usual.

Oh I see! Thank you!!