361. Bomb Enemy : Past Google Coding Interview
Problem
https://leetcode.com/problems/bomb-enemy/
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)
