LC: Bomb Enemy - spiralgo/algorithms GitHub Wiki

The Essence:

Consider this grid for example, where brown tiles are the walls and the green ones are the enemies:

When the procedure starts the counting for each tile, we first start by counting the first column at the first row. Here, 2 for the row and 1 for the column is counted. When the counting continues in the same row, no new walls are encountered, hence the count for this row should not change. The count of this row can be stored in a number and be changed if and only if we encounter a wall, otherwise no new searches are needed at these tiles.

The same things is valid for the columns. Assume that counted the column values up until some end or a wall is counted for some tiles. Since the procedure is not directly iterating through the columns, these values can similarly be kept in an array of numbers for the columns. At the first column, for example, the information found out at [0,0] can be reused, as no new walls are here in the same column.

In places like the 3rd row, the row counter will be reset when it comes across a new wall.

Details:

The procedure here needs two just loops for iteration and is of pseudo-quadratic time complexity, as each tile is processed at most 3 times. Further information and code can be found at: https://github.com/spiralgo/algorithms/pull/313