Water and the grid

#1

There is an island in the form of MxN grid where each cell either has a tower built on it or is empty. Each cell is a square of unit area and each tower has a height of 1 unit.
Monsoon has come and rain has started, The king of the island wants to estimate how much volume of water would be trapped in between the towers.
Water will be trapped, only if it does not reach to the corner and flows out. Water from the current cell can reach to another cell only if that cell shares an edge with the current cell.

Constraints
1<= MxN <= 1000000

INPUT
The first line will contain two integers M and N, then the following lines will contain a grid of MxN, where ‘’* denotes that cell is blocked and ‘.’ denotes that it is empty.

OUTPUT
The output would contain the volume of water trapped.

SAMPLE INPUT

4 4 .**. .. … ****

SAMPLE OUTPUT

3

#2

hello @aattuull
what issue u r facing?

also pls share the problem link with me

#3

Not able to think approach …pls solve this

#4

@aattuull
the idea for this problem is simple
a) count number of buildings. (say count is a)
b) run dfs from all water that are on corners/edge and count them (say it is b)
so answer will be

n*m (total number of grids) - a (count of buildings) - b (count of water on corners/edge )

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.