## Problem: Replace O’s with X’s

*Difficulty: Medium
Given a matrix of size NxM where every element is either ‘O’ or ‘X’, replace ‘O’ with ‘X’ if surrounded by ‘X’. A ‘O’ (or a set of ‘O’) is considered to be by surrounded by ‘X’ if there are ‘X’ at locations just below, just above, just left and just right of it.

Examples:

```Input: mat[N][M] =  {{'X', 'O', 'X', 'X', 'X', 'X'},
{'X', 'O', 'X', 'X', 'O', 'X'},
{'X', 'X', 'X', 'O', 'O', 'X'},
{'O', 'X', 'X', 'X', 'X', 'X'},
{'X', 'X', 'X', 'O', 'X', 'O'},
{'O', 'O', 'X', 'O', 'O', 'O'},
};
Output: mat[N][M] =  {{'X', 'O', 'X', 'X', 'X', 'X'},
{'X', 'O', 'X', 'X', 'X', 'X'},
{'X', 'X', 'X', 'X', 'X', 'X'},
{'O', 'X', 'X', 'X', 'X', 'X'},
{'X', 'X', 'X', 'O', 'X', 'O'},
{'O', 'O', 'X', 'O', 'O', 'O'},
};

```
```Input: mat[N][M] =  {{'X', 'X', 'X', 'X'}
{'X', 'O', 'X', 'X'}
{'X', 'O', 'O', 'X'}
{'X', 'O', 'X', 'X'}
{'X', 'X', 'O', 'O'}
};
Input: mat[N][M] =  {{'X', 'X', 'X', 'X'}
{'X', 'X', 'X', 'X'}
{'X', 'X', 'X', 'X'}
{'X', 'X', 'X', 'X'}
{'X', 'X', 'O', 'O'}
};```

Input:
The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. The first line of each test case contains two integers N and M denoting the size of the matrix. Then in the next line are N*M space separated values of the matrix.

Output:
For each test case print the space separated values of the new matrix.

Constraints:
1<=T<=10
1<=mat[][]<=100
1<=n,m<=20

Example:
Input:

2
1 5
X O X O X
3 3
X X X X O X X X X
Output:
X O X O X
X X X X X X X X X

Approach:
The problem’s description is not clear enough. Just imagine that you’re playing Go, O is black and X is white, if a territory of black is surrounded by white, then all cells in that territory are replaced by white.
Problem’s difficulty is medium because the code is pretty long (I suppose)

Algorithm:
1. Get all O groups
2. From those groups, get groups that are surrounded by X
3. Replace O groups by X
Simple, isn’t it?

Implementation: Python 2.7

```def getAllOGroups(matrix):
markedO, groups = [], []
for i in range(len(matrix)):
for j in range(len(matrix[i])):
if not (i, j) in markedO and matrix[i][j] == 'O':
tempGroup = []
groups.append(tempGroup)
return groups

def getAllAdjacentOFrom(i, j, matrix, tempGroup, markedO):
tempGroup.append((i, j))
markedO.append((i, j))
#up
i_up, j_up = i-1, j
if isInBound(i_up, j_up, matrix) and (i_up, j_up) not in markedO and matrix[i_up][j_up] == 'O':
#down
i_down, j_down = i+1, j
if isInBound(i_down, j_down, matrix) and (i_down, j_down) not in markedO and matrix[i_down][j_down] == 'O':
#left
i_left, j_left = i, j-1
if isInBound(i_left, j_left, matrix) and (i_left, j_left) not in markedO and matrix[i_left][j_left] == 'O':
#right
i_right, j_right = i, j+1
if isInBound(i_right, j_right, matrix) and (i_right, j_right) not in markedO and matrix[i_right][j_right] == 'O':

def getGroupsSurroundedByX(groups, matrix):
surroundedGroups = []
for groupO in groups:
if len([(i, j) for (i,j) in groupO if isSurroundedByX(i, j, matrix)]) == len(groupO):
surroundedGroups.append(groupO)
return surroundedGroups

def isSurroundedByX(i, j, matrix):
xUp = False
for _ in range(i-1, -1, -1):
if matrix[_][j] == 'X':
xUp = True
break
xDown = False
for _ in range(i+1, len(matrix)):
if matrix[_][j] == 'X':
xDown = True
break
xLeft = False
for _ in range(j-1, -1, -1):
if matrix[i][_] == 'X':
xLeft = True
break
xRight = False
for _ in range(j+1, len(matrix[0])):
if matrix[i][_] == 'X':
xRight = True
break
return xUp == xDown == xLeft == xRight == True

def isInBound(i, j, matrix):
return i >= 0 and i < len(matrix) and j >= 0 and j < len(matrix[0])

def replaceOByX(surroundedGroups, matrix):
for group in surroundedGroups:
for (i, j) in group:
matrix[i][j] = 'X'

def printFormated(matrix):
for row in matrix:
for cell in row:
print cell,
print

def main():
t = input()
for _ in range(t):
n, m = map(int, raw_input().strip().split())
arr = raw_input().strip().split()
matrix = [arr[i:i+m] for i in range(0, len(arr), m)]
#get all O-groups
groups = getAllOGroups(matrix)
#get groups that are surrounded by X
surroundedGroups = getGroupsSurroundedByX(groups, matrix)
#replace O with X
replaceOByX(surroundedGroups, matrix)
printFormated(matrix)

if __name__ == '__main__':
main()

```