Matsushita's Blog

361. Bomb Enemy : Past Google Coding Interview


How to Solve

This problem can be solved by using Dynamic Programming. The point of this problem is that one spot in the grid can divide into four direction (up, down, left, right). We can count the number of enemies which we can kill when we drop a bomb at one spot by counting those separately in four direction.

I define spot(i, j) as the number of enemies at the time when I drop a bomb at coordinate (i, j), and spot(i, j).up as the number of enemies in only up direction. Then spot(i, j).up is written as the following recurrence relation.

spot(i, j).up = spot(i - 1, j).up

We can define all direction like as this recurrence relation.

Finally, spot(i, j) is written as the following code.

spot(i, j) = spot(i, j).up + spot(i, j).right + spot(i, j).bottom + spot(i, j).left

The time complexity of this code is O(R*C). (R: number of the row, C : number of the col)

Source Code