**Author:** Praveen Dhinwa

**Tester:** Istvan Nagy

**Editorialist:** Misha Chorniy

## Difficulty:

Simple

# Pre-Requisites:

none

## Problem Statement

You are given matrix which presents a water reservoir, each cell can be water, air or brick. You need to check whether a state of the reservoir is stable or not? The state is stable if it will remain in the same state forever.

## Explanation

## Subtask 1

There are no water cells in matrix. We need to check if no one brick don’t have air under itself. If brick has air under itself, it fall down.

```
ok = true
for i=1..n-1
for j=1..m
if s[i][j]=='B' and s[i+1][j]== 'A' //this block (i, j) will fall down
ok = false
```

## Subtask 2 and 3

Observe that air can’t change something, we are interested in movements of bricks and water. Brick only can fall down, if under isn’t brick. Water can move to the left(if there are empty or air), to the right(if there are empty or air) or move down(if there are nothing or air).

```
ok = true
for i=1..n
for j=1..m
if s[i][j]=='B' and i+1<=n and s[i+1][j]!='B' // brick (i, j) fall down
ok = false
if s[i][j]=='W'
if j==1 or j==m or i==n //water overflow bounds
ok = false
else if s[i][j-1]=='A' or s[i][j+1]=='A' or s[i+1][j]=='A' //water can move into adjacent blocks(left, right, down)
ok = false
```

Overall time complexity of this approach is O(N*M).

## Solution:

Setter’s solution can be found here

**Please feel free to post comments if anything is not clear to you.**