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 = []
                #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()

Advertisements