##### Short Problem Definition:

You are given a square map of size n×n. Each cell of the map has a value denoting its depth. We will call a cell of the map a cavity if and only if this cell is not on the border of the map and each cell adjacent to it has **strictly smaller depth**. Two cells are adjacent if they have a common side.

##### Link

##### Complexity:

time complexity is `O(N^2)`

space complexity is `O(1)`

##### Execution:

*pun* You only get your cavities checked on an airport */pun*

I check all 4 surrounding elements if they are strictly smaller. If so, I mark the position with an ‘X’. Better runtime than n^2 is not possible as every element has to be visited!

##### Solution:

```
#!/usr/bin/py
def transformCavity(arr, n):
for idx_tb in xrange(1, n-1):
for idx_lr in xrange(1, n-1):
if arr[idx_tb-1][idx_lr] != 'X' and int(arr[idx_tb-1][idx_lr]) < int(arr[idx_tb][idx_lr]) and \
arr[idx_tb+1][idx_lr] != 'X' and int(arr[idx_tb+1][idx_lr]) < int(arr[idx_tb][idx_lr]) and \
arr[idx_tb][idx_lr-1] != 'X' and int(arr[idx_tb][idx_lr-1]) < int(arr[idx_tb][idx_lr]) and \
arr[idx_tb][idx_lr+1] != 'X' and int(arr[idx_tb][idx_lr+1]) < int(arr[idx_tb][idx_lr]):
arr[idx_tb][idx_lr] = 'X'
if __name__ == '__main__':
n = input()
arr = []
for _ in xrange(n):
line = list(raw_input())
arr.append(line)
transformCavity(arr, n)
for line in arr:
print ''.join(line)
```