Tree Knapsack Problem

sakibalamin AUST ACM Lab 02 Selection...
Limits 1s, 512 MB

Akash loves maths, but being from Rajshahi, he also loves mangoes. That is why he has a large mango tree In his backyard. But due to the COVID-19 outbreak, he is stuck in Dhaka.

Now that there is nobody to defend his mango tree, vector94, conveniently from Rajshahi, decides to steal some of his mangoes.

He stands under Akash’s mango tree with a large knapsack, and shoots at all of his mangoes.
When a mango is shot, it falls down.

Just as he is done shooting, lockdown begins again, and he has to return home quickly. As a result, he cannot collect all mangoes, and just returns with the mangoes that fell directly on his knapsack.

Can you find how many mangoes fell directly on top of his knapsack?

You are given a 2D grid corresponding to the situation of R rows and C columns.

Mangoes are labelled as ‘O’,

The tree is labelled as ‘t’, for simplicity, you can assume the mangos can fall through trees.

Leaves are labelled as ‘g’. You can assume that mangoes can fall through leaves.

The knapsack is represented by one straight horizontal strip of ‘=’. You can assume it has infinite capacity.

The ground is labeled as ‘a’. Mangoes cannot pass through the ground.

You can assume the knapsack does not go through the stem of the tree.

Input

First line contains two positive integers, R and C — the number of rows and columns respectively.
(1 ≤ R,C ≤ 500)
Each of the next R lines will contain C characters describing the grid.

Output

Print one integer, the number of mangoes that fell directly on top of his knapsack.

Samples

InputOutput
8 16
................
....t..O...t.t..
.O.tt.....t..O..
.....t..t.......
...O...t........
.......t........
.......t...====.
aaaaaaaaaaaaaaaa
1

It can be clearly seen that there is one mango over the knapsack.

InputOutput
33 55
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
..............................g...g....................
..................g....g....g........g.................
..............g..........g.............................
...........g...........................g...............
.........g.........................O.....g.............
........g.......O.......t.....t............g...........
......g.....O...........t....t.........................
.....g...................t.t.................g.........
...g........t............tt....t.......t...............
....g........t......t....t..t......t........gg.........
....g.........t....t.........t....tttt.................
....g.....O....t.t............t...t.......O............
....g...........t............t.tt.O....................
.....g..........t...........tt..............g..........
......g.....tttttt..........t........O.................
........g....t....tt.......t.....O.........g...........
..........g.........tt....t............................
............g.g......tt..t.............g...............
...............g......ttt.....g..g..g.g................
.................g....ttt..g...........................
...................g.gtttg.............................
......................ttt..............................
......................ttt..............................
......................ttt..............................
......................ttt..............................
......................ttt......=========...............
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
4

vector94's knapsack can be anywhere, and it will not move.

Submit

Login to submit.

Statistics

86% Solution Ratio
FairoozREarliest, Jun '20
riyad000Fastest, 0.0s
KhandokerananLightest, 5.5 kB
Abdullah_1234Shortest, 236B
Toph uses cookies. By continuing you agree to our Cookie Policy.