*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 = []
#get all adjacent O
getAllAdjacentOFrom(i, j, matrix, tempGroup, markedO)
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':
getAllAdjacentOFrom(i_up, j_up, matrix, tempGroup, markedO)
#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':
getAllAdjacentOFrom(i_down, j_down, matrix, tempGroup, markedO)
#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':
getAllAdjacentOFrom(i_left, j_left, matrix, tempGroup, markedO)
#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':
getAllAdjacentOFrom(i_right, j_right, matrix, tempGroup, markedO)
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()

## Reply