# マツシタのお勉強メモ

#### マツシタのお勉強

##### welcome to my engineering blog
###### Hacker Rank # 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)