Fast 15x15 bit grid BFS: breadth first search

Update: 06.04.2020: Mlomb found several bugs in the code with his testing. Assignment to return value was too late (after break). There was a bit shift in incorrect direction. Initialization of available was incorrect (missing a few bits: 2 * 15 != 264 - 15 * 15 hehe). Performance suffered a bit with these corrections, but still getting around 1 million. After these corrections mlomb tested the code against his own BFS implementation and validated with 0 errors of 999901 test cases.

Each presence of anything on the map is represented as a bit set to 1 and absence of anything is the bit set to 0. To get the neighbours of current set cells we shift bits left, right, up or down and then to get both we take the union with current set cells (bitwise or). To restrict from going into unavailable cells we do intersection (bitwise and) with inversion (bitwise not) of unavailable cells. As we said the last row and column are unavailable, and also "islands" (in this case for Ocean of Code) are unavailable.

The optimization idea is to split the board into white and black cells by odd and even indices, like a chess board. In that way black cells only have white neighbours and white cells only have black neighbours.

Leave a Comment