CareerCup

#include <iostream>
#include <string>
#include <vector>

using namespace std;

void fillWithY(vector<string>& A, int i, int j)
{
    if (i < 0 || i >= A.size() || j < 0 || j >= A[i].size() || A[i][j] != 'O')
        return;

    A[i][j] = 'Y';

    fillWithY(A, i - 1, j); // absorb more 'O' on the top
    fillWithY(A, i + 1, j); // absorb more 'O' on the bottom
    fillWithY(A, i, j - 1); // absorb more 'O' on the left
    fillWithY(A, i, j + 1); // absorb more 'O' on the right
}

int main()
{
    vector<string> A;

    A.push_back("XXXXX");
    A.push_back("XXOOX");
    A.push_back("XXOOX");
    A.push_back("OXXXX");
   
    // first try to aborb '0's at the boundary and replace them with 'Y'
    for (int j = 0; j < A[0].size(); j++) 
        fillWithY(A, 0, j); 

    for (int j = 0; j < A.back().size(); j++) 
        fillWithY(A, A.size() - 1, j);

    for (int i = 0; i < A.size(); i++) {
        fillWithY(A, i, 0); 
        fillWithY(A, i, A[i].size() - 1); 
    }

    // rewrite internal 'O's with 'X', and restore 'Y's
    for (int i = 0; i < A.size(); i++) {
        for (int j = 0; j < A[i].size(); j++)
            if (A[i][j] == 'Y')
                A[i][j] = 'O';
            else if (A[i][j] == 'O')
                A[i][j] = 'X';
    }

    // shown me the result
    for (int i = 0; i < A.size(); i++) 
        cout << A[i] << endl;
}

1) Scan the array in concentric squares outside in.
2) Mark all 'O' elements as 'o' if any of the 8 elements surrounding it is an 'o' or its on the edge. In case neither of the above is true change it to 'X'
3) In the end scan through the array and convert all 'o' to 'O'

this question is the opposite of leetcode oj (surrounded-regions)

public class Solution {
    public void solve(char[][] board) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(board==null || board.length<3 || board[0].length<3){
            
        }
        else{
            for(int i=0; i<board.length; i++){
                if(board[i][0]=='O'){
                    expand(board, i, 0);
                }
                if(board[i][board[0].length-1]=='O'){
                    expand(board, i, board[0].length-1);
                }
            }
            for(int i=0; i<board[0].length; i++){
                if(board[0][i]=='O'){
                    expand(board, 0, i);
                }
                if(board[board.length-1][i]=='O'){
                    expand(board, board.length-1, i);
                }
            }
            
            
            for(int i=0; i<board.length; i++){
                for(int j=0; j<board[0].length; j++){
                    if(board[i][j]=='-'){
                        board[i][j]='O';
                    }
                }
            }
        }
    }
    
    public void expand(char[][] board, int row, int col){
        board[row][col] = '-';
        if((row==0&&col==0) || (row==board.length-1&&col==board[0].length-1) || 
            (row==0&&col==board[0].length-1) || (row==board.length-1&&col==0)){
            
        }
        else if(row==0){
            if(board[row+1][col]=='O'){
                expand(board, row+1, col);
            }
        }
        else if(col==0){
            if(board[row][col+1]=='O'){
                expand(board, row, col+1);
            }
        }
        else if(row==board.length-1){
            if(board[row-1][col]=='O'){
                expand(board, row-1, col);
            }
        }
        else if(col==board[0].length-1){
            if(board[row][col-1]=='O'){
                expand(board, row, col-1);
            }
        }
        else{
            if(board[row+1][col]=='O'){
                expand(board, row+1, col);
            }
        
            if(board[row][col+1]=='O'){
                expand(board, row, col+1);
            }

            if(board[row-1][col]=='O'){
                expand(board, row-1, col);
            }

            if(board[row][col-1]=='O'){
                expand(board, row, col-1);
            }
        }
    }
}

// 
// "XOXOXOOOXO",
// "XOOXXXOOOX",
// "OOOOOOOOXX",
// "OOOOOOXOOX",
// "OOXXOXXOOO",
// "XOOXXXOXXO",
// "XOXOOXXOXO",
// "XXOXXOXOOX",
// "OOOOXOXOXO",
// "XXOXXXXOOO"

For an NxN board, I found a solution O(N^2) time. The worst case space is also O(N^2) when all the cell values are "O". But for random input it will be much less (the space is due to stack for recursion).

The only logical clue I found is that if there is an "O" on the border, then any it along with all the connected "O"'s won't turn into "X".

In my code I treat "0" as X and "1" as "O". Also, "fillup()" is the function to call and it will use "spread(i, j)" to mark the "O"'s that won't convert into "X".
Code in C:

int* mat;
void init() {
	mat = (int*) malloc(sizeof(int) * WIDTH * HEIGHT);
};

void spread(int i, int j) {
  if (CELL(mat, i, j) == 1) {
    CELL(mat, i, j) = 2;    
  }
  else
    return;
  if (i < HEIGHT - 1)
    spread(i + 1, j);
  if (i > 1)
    spread(i - 1, j);
  if (j > 1)
    spread(i, j - 1);
  if (j < WIDTH - 1)
    spread(i, j + 1);
}
void fillup() {
  int i = 0;
  // side columns
  for (i = 0; i < HEIGHT; i++) {
    if (CELL(mat, i, 0)) {
      spread(i, 0);
    };
    if (CELL(mat, i, WIDTH - 1)) {
      spread(i, WIDTH - 1);
    };
  }
  // top-bottom rows
  for (i = 0; i < WIDTH; i++) {
    if (CELL(mat, 0, i)) {
      spread(0, i);
    };
    if (CELL(mat, HEIGHT - 1, i)) {
      spread(HEIGHT - 1, i);
    };
  };
  for (i = 0; i < HEIGHT; i++) {
    int j;
    for (j = 0; j < WIDTH; j++) {
      CELL(mat, i, j) = 1 ? CELL(mat, i, j) > 1 : 0;
    };
  };
};

TEST (first input then output):

X       X       X       X       X       X       X       X       X       X
X       X       X       X       X       O       O       X       X       X
X       X       X       X       X       O       O       X       X       X
X       X       X       X       X       X       X       X       X       X
X       X       X       X       X       X       X       X       X       X
X       X       X       X       X       X       X       X       X       X
X       X       X       X       X       X       O       O       O       X
X       X       X       X       X       X       X       O       X       X
X       O       O       O       X       X       X       X       X       X
X       O       X       X       X       X       X       X       X       X
Finished the paint...
X       X       X       X       X       X       X       X       X       X
X       X       X       X       X       X       X       X       X       X
X       X       X       X       X       X       X       X       X       X
X       X       X       X       X       X       X       X       X       X
X       X       X       X       X       X       X       X       X       X
X       X       X       X       X       X       X       X       X       X
X       X       X       X       X       X       X       X       X       X
X       X       X       X       X       X       X       X       X       X
X       O       O       O       X       X       X       X       X       X
X       O       X       X       X       X       X       X       X       X

void replace(char *a,int rows,int cols) /* passed array has to be 2d char array */
{
int k,i,j;
for(i=1;i<rows-1;i++) /* Skippiing the scanning of first an last row */
{
for (j=1;j<cols-1;j++) /* Skippiing the scanning of first an last column */
{
if(*(a+i*cols+j)=='o')
{
for(k=i;k<cols;k++)
{
if (*(a+k*cols+j)=='x')
break;
}
if(k==cols) break;
for(k=i;k>=0;k--)
{
if (*(a+k*cols+j)=='x')
break;
}
if(k==-1) break;
for(k=j;k>=0;k--)
{
if (*(a+i*cols+k)=='x')
break;
}
if(k==-1) break;
for(k=j;k<rows;k--)
{
if (*(a+i*cols+k)=='x')
break;
}
if(k==rows)
break;

*(a+i*cols+j)='x';
}
}
}
}

// identify the cells which are O and are surrounded
bool isSurrounded(int i, int j)
{
	bool top, bottom, left, right = true;
	bool returnValue = true;
	visited[i][j] = true;
	if(j > 0)
	{
		if(matrix[i][j-1] == 'O' && visited[i][j-1] != true)
		{
			top = isSurrounded(i, j-1);
		}
	}
	else if(matrix[i][j] == 'O')
	{
		returnValue = false;
	}

	if(j < MAXJ)
	{
		if(matrix[i][j+1] == 'O' && visited[i][j+1] != true)
		{
			bottom = isSurrounded(i, j+1);
		}
	}
	else if(matrix[i][j] == 'O')
	{
		returnValue = false;
	}

	if(i > 0)
	{
		if(matrix[i-1][j] == 'O' && visited[i-1][j] != true)
		{
			left = isSurrounded(i-1, j);
		}
	}
	else if(matrix[i-1][j] == 'O')
	{
		returnValue = false;
	}

	if(i < MAXI)
	{
		if(matrix[i+1][j] == 'O' && visited[i+1][j] != true)
		{
			right = isSurrounded(i+1, j);
		}
	}
	else if(matrix[i+1][j] == '0')
	{
		returnValue = false;
	}

	return returnValue && top && bottom && left && right;
}

// mark all Xs with Os by looking at the visited matrix
bool mark(int i, int j)
{
	matrix[i][j] = 'O';
	visited[i][j] = false;

	if(i > 0)
	{
		if(visited[i-1][j])
			mark(i-1, j);
	}

	if(i < MAXI)
	{
		if(visited[i+1][j])
			mark(i+1, j);
	}

	if(j > 0)
	{
		if(visited[i][j-1])
			mark(i, j-1);
	}

	if(j < MAXJ)
	{
		if(visited[i][j+1])
			mark(i, j+1);
	}
}

void main()
{
	for(int i = 0; i <= MAXI; i++)
	{
		for(int j = 0; j <= MAXJ; j++)
		{
			if(matrix[i][j] == 'O' && visited[i][j] == false)
			{
				if(isSurrounded(i, j))
				{
					// an isolated region exists, mark all Xs with Os
					mark(i, j);
				}
			}
		}
	}
}

import java.util.ArrayList;
import java.util.List;

public class Solution {

    public static char[][] fillMatrix0(char[][] m) {
        
        int rows = m.length;
        int cols = m[0].length;
        char[][] ret = new char[rows][cols];
        List<String> posList = new ArrayList<String>();
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                
                if (m[i][j] == 'O' && ret[i][j] != 'X') {                	
                	posList.clear();
                	posList.add(i + "," + j);
                    if (isSurroundedByX(posList, m, i, j)) {                    	
                    	// mark X for all found in block
                    	for (String string : posList) {							
                    		// expecting format i,j
                    		int posI = Integer.parseInt(string.substring(0, 1));
                    		int posJ = Integer.parseInt(string.substring(2, 3));                    		
                    		ret[posI][posJ] = 'X';
						}
                    } else {
                        ret[i][j] = 'O';
                    }
                } else {
                    ret[i][j] = 'X';
                }                
            }
        }
        
        return ret;
    }
    
    public static boolean isSurroundedByX(List<String> positionList, char[][] m, int i, int j) {
        if (m == null || m.length == 0) {
            return false;
        }
        
        int rows = m.length;
        int cols = m[0].length;
        
        // test boundary
        if (i == 0 || i == rows - 1) {
            return false;
        }
        if (j == 0 || j == cols - 1) {
            return false;
        }
        
        // check up, 
        if (m[i - 1][j] == 'O' && !positionList.contains((i - 1) + "," + j)) {        	        	
        	positionList.add( (i - 1) + "," + j);
        	if (!isSurroundedByX(positionList, m, i - 1, j)) {
        		return false;
        	}
        }
        // check right
        if (m[i][j + 1] == 'O' && !positionList.contains((i) + "," + (j + 1))) {        
        	positionList.add( (i) + "," + (j + 1) );
        	
        	if (!isSurroundedByX(positionList, m, i, j + 1)) {
        		return false;	
        	}            
        }
        // check down
        if (m[i + 1][j] == 'O' && !positionList.contains((i + 1) + "," + j)) {
        	positionList.add( (i + 1) + "," + j );
        	
        	if (!isSurroundedByX(positionList, m, i + 1, j)) {
        		return false;	
        	}
        }
        // check left
        if (m[i][j - 1] == 'O' && !positionList.contains(i + "," + (j - 1))) {
        	positionList.add( i + "," + (j - 1) );
        	
        	if (!isSurroundedByX(positionList, m, i, j - 1)) {
        		return false;	
        	}
        }
        return true;
    } 

    public static void printMatrixResults(char[][] ret) {
        int rows = ret.length;
        int cols = ret[0].length;
        
        // print results
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                System.out.print(ret[i][j] + " ");    
            }
            System.out.println();
        }    	
    }
    
    public static void runSampleTests() {
    
    /*
    	X X X X X 
    	X X O O X 
    	X X O O X 
    	O X X X X
    */
    
    char[][] m = new char[4][5];
    
    m[0][0] = 'X';
    m[0][1] = 'X';
    m[0][2] = 'X';
    m[0][3] = 'X';
    m[0][4] = 'X';

    m[1][0] = 'X';
    m[1][1] = 'X';
    m[1][2] = 'O';
    m[1][3] = 'O';
    m[1][4] = 'X';

    m[2][0] = 'X';
    m[2][1] = 'X';
    m[2][2] = 'O';
    m[2][3] = 'O';
    m[2][4] = 'X';

    m[3][0] = 'O';
    m[3][1] = 'X';
    m[3][2] = 'X';
    m[3][3] = 'X';
    m[3][4] = 'X';
    
    char[][] ret = fillMatrix0(m);
    printMatrixResults(ret);

    /*
	X X X X X 
	X X O O X 
	X X O O O 
	O X X X X
*/
	m = new char[4][5];
	
	m[0][0] = 'X';
	m[0][1] = 'X';
	m[0][2] = 'X';
	m[0][3] = 'X';
	m[0][4] = 'X';
	
	m[1][0] = 'X';
	m[1][1] = 'X';
	m[1][2] = 'O';
	m[1][3] = 'O';
	m[1][4] = 'X';
	
	m[2][0] = 'X';
	m[2][1] = 'X';
	m[2][2] = 'O';
	m[2][3] = 'O';
	m[2][4] = 'O';
	
	m[3][0] = 'O';
	m[3][1] = 'X';
	m[3][2] = 'X';
	m[3][3] = 'X';
	m[3][4] = 'X';
		
	char[][] ret1 = fillMatrix0(m);
	System.out.println();
	printMatrixResults(ret1);
    }
    
    public static void main(String args[]) {
    	runSampleTests();
    }    
}

Pretty much the same approach as Westlake, written in Java.

public class FindOSurround {
	private static final char X = 'X';
	private static final char O = 'O';
	private static final char Y = 'Y';
	private static final Board board1 = new Board(new char[][] {
			{X,X,X,X,X},
			{X,X,O,O,X},
			{X,X,O,O,X},
			{O,X,X,X,X},
	});
	private static final Board board2 = new Board(new char[][] {
			{X,X,X,X,X},
			{X,X,O,O,X},
			{X,X,O,O,O},
			{O,X,X,X,X},
	});
	
	private static void fillEdgeTouchingOs(Board b, int x, int y) {
		if(x < 0 || y < 0 || b.getX() <= x || b.getY() <= y || b.getValue(x, y) != O) {
			return;
		}
		
		b.setValue(x, y, Y);

		fillEdgeTouchingOs(b, x-1, y);
		fillEdgeTouchingOs(b, x+1, y);
		fillEdgeTouchingOs(b, x, y-1);
		fillEdgeTouchingOs(b, x, y+1);
	}

	// Strategy: Go around edges, find any O. mark it and touching O's to Y's
	public static void fillXSurroundedOs(Board b) {
		final int lastX = b.getX()-1;
		final int lastY = b.getY()-1;
		// X-Axis
		for(int x=0; x < b.getX(); ++x) {
			fillEdgeTouchingOs(b, x, 0);
			fillEdgeTouchingOs(b, x, lastY);
		}
		// Y-Axis
		for(int y=0; y < b.getY(); ++y) {
			fillEdgeTouchingOs(b, 0, y);
			fillEdgeTouchingOs(b, lastX, y);
		}
		
		// Fill remaining O's with X because they must be surrounded by X
		for(int x=0; x < b.getX(); ++x) {
			for(int y=0; y < b.getY(); ++y) {
				if(b.getValue(x, y) == O) {
					b.setValue(x, y, X);
				}
			}
		}
		
		// Reset state of Y's back to O
		for(int x=0; x < b.getX(); ++x) {
			for(int y=0; y < b.getY(); ++y) {
				if(b.getValue(x, y) == Y) {
					b.setValue(x, y, O);
				}
			}
		}
	}
	
	private static void printFillResults(Board b) {
		System.out.println("Starting Board");
		System.out.println("Before:");
		System.out.println(b);
		fillXSurroundedOs(b);
		System.out.println("After:");
		System.out.println(b);
		System.out.println("Done with Board");
	}
	
	public static void main(String[] args) {
		printFillResults(board1);
		printFillResults(board2);
	}
	
	private static final class Board {
		private final char[][] board;
		
		public Board(char[][] board) {
			this.board = board;
			
			if(board.length == 0) {
				throw new IllegalArgumentException("No length");
			}

			
			final int expectedLength = board[0].length;
			if(expectedLength == 0) {
				throw new IllegalArgumentException("No length");
			}
			
			for(char[] xRow : board) {
				if(expectedLength != xRow.length) {
					throw new IllegalArgumentException("Board must be rectangle");
				}
			}
		}
		
		public int getX() {
			return board.length;
		}
		
		public int getY() {
			return board[0].length;
		}
		
		public char getValue(int x, int y) {
			return board[x][y];
		}
		
		public void setValue(int x, int y, char v) {
			this.board[x][y] = v;
		}
		
		public String toString() {
			StringBuilder sb = new StringBuilder();

			for(int x=0; x < getX(); ++x) {
				for(int y=0; y < getY(); ++y) {
					sb.append(getValue(x,y)).append(" ");
				}
				sb.append('\n');
			}
			return sb.toString();
		}
	}
}

public class MatrixFill {

	static int N = 10;
	static int M = 11;
	static int order = 0;
	static char[][] matrix = new char[N][M];

	public static void main(String[] args) {
		matrix[0] = "XXXXXXXXXXX".toCharArray();
		matrix[1] = "XXXXOOXXXXX".toCharArray();
		matrix[2] = "XXXXOOXXXXX".toCharArray();
		matrix[3] = "XXXXXXXXXXX".toCharArray();
		matrix[4] = "XXXXXXOXXXX".toCharArray();
		matrix[5] = "XXXXXXOXXXX".toCharArray();
		matrix[6] = "XXXXXXOXXXX".toCharArray();
		matrix[7] = "XXXXXXOXXXX".toCharArray();
		matrix[8] = "XXXXXXOOOOO".toCharArray();
		matrix[9] = "XXXXXXXXXXX".toCharArray();

		printMatrix();
		substitute('O');
		compute();
		substitute('1', 'X');
		substitute('0', 'O');
		printMatrix();
	}

	private static void printMatrix() {
		System.out.println(order);
		for (int i = 0; i < N; i++) {
			System.out.println(String.valueOf(matrix[i], 0, M));
		}
		System.out.println();
	}

	private static void compute() {
		boolean changed = true;
		while (changed) {
			printMatrix();
			order++;
			changed = false;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					if (matrix[i][j] != 'X') {
						changed = computeCell(i, j) || changed;
					}
				}
			}
		}
	}

	private static boolean computeCell(int i, int j) {
		char value = matrix[i][j];
		if (j > 0) {
			matrix[i][j] = multiply(i, j, i, j - 1);
		}
		if (i > 0) {
			matrix[i][j] = multiply(i, j, i - 1, j);
		}
		if (j < N - 1) {
			matrix[i][j] = multiply(i, j, i, j + 1);
		}
		if (i < N - 1) {
			matrix[i][j] = multiply(i, j, i + 1, j);
		}
		return value != matrix[i][j];
	}

	private static char multiply(int i, int j, int x, int y) {
		if (matrix[x][y] == 'X')
			return matrix[i][j];
		return matrix[x][y] == '0' ? '0' : matrix[i][j];
	}

	private static void substitute(char c) {
		order++;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (matrix[i][j] == c) {
					if (i == 0 || i == N - 1 || j == 0 || j == N - 1) {
						matrix[i][j] = '0';
					} else {
						matrix[i][j] = '1';
					}
				}
			}
		}
	}

	private static void substitute(char c, char d) {
		order++;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (matrix[i][j] == c)
					matrix[i][j] = d;
			}
		}
	}

}

package misc;

public class MatrixFill {

	static int N = 10;
	static int M = 11;
	static int order = 0;
	static char[][] matrix = new char[N][M];

	public static void main(String[] args) {
		matrix[0] = "XXXXXXXXXXX".toCharArray();
		matrix[1] = "XXXXOOXXXXX".toCharArray();
		matrix[2] = "XXXXXXXXXXX".toCharArray();
		matrix[3] = "XOXXXXOOOXX".toCharArray();
		matrix[4] = "XOOOXXXXOXX".toCharArray();
		matrix[5] = "XXXOXXXXOXX".toCharArray();
		matrix[6] = "XOOOXXOOOXX".toCharArray();
		matrix[7] = "XOXXXXXXXXX".toCharArray();
		matrix[8] = "XOOOOOOOOOO".toCharArray();
		matrix[9] = "XXXXXXXXXXX".toCharArray();

		printMatrix();
		substitute('O');
		compute();
		substitute('1', 'X');
		substitute('0', 'O');
		printMatrix();
	}

	private static void printMatrix() {
		System.out.println(order);
		for (int i = 0; i < N; i++) {
			System.out.println(String.valueOf(matrix[i], 0, M));
		}
		System.out.println();
	}

	private static void compute() {
		boolean changed = true;
		while (changed) {
			printMatrix();
			order++;
			changed = false;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					if (matrix[i][j] != 'X') {
						changed = computeCell(i, j) || changed;
					}
				}
			}
		}
	}

	private static boolean computeCell(int i, int j) {
		char value = matrix[i][j];
		int x, y;
		for (x = i, y = j; y < M && matrix[x][y] != 'X'; y++) {
			multiply(i, j, x, y);
		}
		for (x = i, y = j; y > 0 && matrix[x][y] != 'X'; y--) {
			multiply(i, j, x, y);
		}
		for (x = i, y = j; x < N && matrix[x][y] != 'X'; x++) {
			multiply(i, j, x, y);
		}
		for (x = i, y = j; x > 0 && matrix[x][y] != 'X'; x--) {
			multiply(i, j, x, y);
		}
		return value != matrix[i][j];
	}

	private static void multiply(int i, int j, int x, int y) {
		if (matrix[x][y] != 'X') {
			matrix[i][j] = matrix[x][y] == '0' ? '0' : matrix[i][j];
			matrix[x][y] = matrix[i][j] == '0' ? '0' : matrix[x][y];
		}
	}

	private static void substitute(char c) {
		order++;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (matrix[i][j] == c) {
					if (i == 0 || i == N - 1 || j == 0 || j == M - 1) {
						matrix[i][j] = '0';
					} else {
						matrix[i][j] = '1';
					}
				}
			}
		}
	}

	private static void substitute(char c, char d) {
		order++;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (matrix[i][j] == c)
					matrix[i][j] = d;
			}
		}
	}

}

I think this can be done with a queue or stack.

- Scan through the array until you reach an O. Add this to a temporary array

- Look at the 8 locations around the O.
--- If any are blank space, return false
--- If any are X, continue looking
--- If any are O, add them to the queue and the temporary array then mark it as visited

- Then take the next O off the queue. If the queue is empty, return true

- If true, change the O's in the temporary array to X's

- Continue the search with the next unvisited O

Dynamic Programming.

surrounded region (leetcode)

import java.util.*;
class Node{
	int x;
	int y;
	Node(int x, int y)
	{
		this.x=x;
		this.y=y;
	}
}
public class Matrix1 {
	
	static char[][] BFS(char[][] inp,int x , int y)
	{
		Queue<Node> q=new LinkedList<Node>();
		q.add(new Node(x,y));
		while(!q.isEmpty())
		{
			Node n=q.poll();
			inp[n.x][n.y]='F';
			//Check up
			if(n.x-1 >=0 && inp[n.x-1][n.y]=='O')
				q.add(new Node(n.x-1,n.y));
			//Check down
			if(n.x+1 < inp.length && inp[n.x+1][n.y]=='O')
				q.add(new Node(n.x+1,n.y));
			//Check left
			if(n.y-1 >=0 && inp[n.x][n.y-1]=='O')
				q.add(new Node(n.x,n.y-1));
			//Check right
			if(n.y+1 < inp[0].length && inp[n.x][n.y+1]=='O')
				q.add(new Node(n.x,n.y+1));
		}
		return inp;
	}
	static char[][] convertMatrix(char[][] inp)
	{
		//find all the 'O' at the boundaries
		for(int i=0; i < inp.length;i=i+(inp.length-1))
		{
			for(int j=0; j < inp[i].length;j++)
			{
				if(inp[i][j]=='O')
				{
					//Do BFS
					inp=BFS(inp,i,j);
				}
			}
		}
		//
		for(int i=0; i < inp[0].length;i=i+inp[0].length-1)
		{
			for(int j=1; j < inp.length-1;j++)
			{
				if(inp[j][i]=='O')
				{
					//Do BFS
					inp=BFS(inp,j,i);
				}
			}
		}
		//Traverse and change
		for(int i=0; i < inp.length;i++)
		{
			for(int j=0; j < inp[i].length;j++)
			{
				if(inp[i][j]=='O')
					inp[i][j]='X';
				else if(inp[i][j]=='F')
					inp[i][j]='O';
				System.out.print(inp[i][j]);
			}
			System.out.println();
		}
		return inp;
	}
	public static void main(String[] args) {
		char[][] inp={{'X','X','X','X','X'},{'X','X','O','O','X'},{'X','X','O','O','O'},{'O','X','X','X','X'}};
		inp=convertMatrix(inp);
	}
}

1. Go through the cells near border. Replace 'O' cells and their 'O' neighbors recursively with ' '.
2. Go through all cells. Replace left 'O' cell values with 'X', ' ' - with 'O'.

package google;

import org.junit.Test;

import static org.junit.Assert.assertArrayEquals;

public class FillMatrixCells {
    @Test
    public void test() {
        Matrix m = new Matrix(new char[][] {
            {'X', 'X', 'X', 'X', 'X'},
            {'X', 'X', 'O', 'O', 'X'},
            {'X', 'X', 'O', 'O', 'X'},
            {'O', 'X', 'X', 'X', 'X'},
        });
        m.fillWrapped();

        char[][] expected = {
                {'X', 'X', 'X', 'X', 'X'},
                {'X', 'X', 'X', 'X', 'X'},
                {'X', 'X', 'X', 'X', 'X'},
                {'O', 'X', 'X', 'X', 'X'},
        };
        char[][] actual = m.getMatrix();

        for (int i = 0; i < actual.length; i++) {
            assertArrayEquals(expected[i], actual[i]);
        }
    }

    public static class Matrix {
        private char[][] m;

        public Matrix(char[][] m) {
            this.m = m;
            validateMatrix();
        }

        public void fillWrapped() {
            if (m.length < 3 || m[0].length < 3) {
                return;
            }

            for (int y = 0; y < m[0].length; y++) {
                replace('O', ' ', 0, y);
                replace('O', ' ', m.length - 1, y);
            }

            for (int x = 1; x < m.length - 1; x++) {
                replace('O', ' ', x, 0);
                replace('O', ' ', x, m[0].length - 1);
            }

            for (int x = 0; x < m.length; x++) {
                for (int y = 0; y < m[0].length; y++) {
                    if (m[x][y] == 'O') {
                        m[x][y] = 'X';
                    } else if (m[x][y] == ' ') {
                        m[x][y] = 'O';
                    }
                }
            }
        }

        public char[][] getMatrix() {
            return m;
        }

        private void replace(char from, char to, int x, int y) {
            if (x < 0 || x >= m.length || y < 0 || y >= m[0].length) return;
            if (m[x][y] == from) {
                m[x][y] = to;
                replace(from, to, x - 1, y);
                replace(from, to, x + 1, y);
                replace(from, to, x, y - 1);
                replace(from, to, x, y + 1);
            }
        }

        private void validateMatrix() {
            if (m.length == 0) return;
            int cols = m[0].length;
            for (int i = 1; i < m.length; i++) {
                if (m[i].length != cols) {
                    throw new IllegalArgumentException("Rows of the matrix have different lengths.");
                }
            }
        }
    }
}

Python code. Assuming that an input like:

X X X X X 
X O X X X 
X X O O X 
X X O O X
O X X X X

should return

X X X X X 
X O X X X 
X X O O X 
X X O O X
O X X X X

Code:

def fill(m):
    o_coor = set([])
    for r, row in enumerate(m):
        for c in range(0, len(row)):
            if row[c] == "O":
                o_coor.add((r,c))

    print o_coor

    while len(o_coor) != 0:
        s = o_coor.pop()
        region = []
        touch = False
        q = []
        q.append(s)

        while len(q) != 0:
            x = q.pop(0)
            region.append(x)
            if (x[0]==0) or (x[0]==(len(m)-1)) or (x[1]==0) or (x[1]==(len(m[0])-1)):
                touch = True
            adjacent = [ ((x[0]-1),x[1]), ((x[0]+1),x[1]), (x[0],(x[1]-1)), (x[0],(x[1]+1)) ]
            for a in adjacent:
                if (a[0] >= 0) and (a[0] < len(m)) and (a[1] >= 0) and (a[1] < len(m[0])) and \
                    (m[a[0]][a[1]] == "O") and ((a[0],a[1]) in o_coor):
                    q.append((a[0],a[1]))
                    o_coor.remove((a[0],a[1]))

        if not touch:
            draw = True
            for x in region:
                r = x[0]
                c = x[1]
                corners = [ (r-1,c-1,r,c-1,r-1,c), \
                            (r+1,c-1,r,c-1,r+1,c), \
                            (r-1,c+1,r-1,c,r,c+1), \
                            (r+1,c+1,r,c+1,r+1,c) ]
                for y in corners:
                    if m[y[0]][y[1]] == "O" and m[y[2]][y[3]] == "X" and \
                        m[y[4]][y[5]] == "X":
                        draw = False
                        break
                if not draw:
                    break
            if draw:
                for x in region:
                    y = list(m[x[0]])
                    y[x[1]] = "X"
                    m[x[0]] = "".join(y)

    return m
                
#main
m = [ "XXXXX", \
      "XOXXX", \
      "XOOXX", \
      "XXXXO"]
print fill(m)

bool fill_with_char(char** a, int m, int n, int x, int y, char c)
{
    if (x < 0 || y < 0 || x >= m || y >= n) return false;
    if (a[x][y] == 'X' || a[x][y] == c) return true;
    a[x][y] = c;
    bool r = true;
    r &= fill_with_char(a, m, n, x+1, y, c);
    r &= fill_with_char(a, m, n, x-1, y, c);
    r &= fill_with_char(a, m, n, x, y+1, c);
    r &= fill_with_char(a, m, n, x, y-1, c);
    return r;
}

void fill_shape(char** a, int m, int n)
{
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            if (a[i][j] == 'O')
                if (fill_with_char(a, m, n, i, j, 'V'))
                    fill_with_char(a, m, n, i, j, 'X');
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            if (a[i][j] == 'V')
                a[i][j] = 'O';
}

void print_matrix(char** a, int m, int n)
{
    std::cout << std::endl;
    for (auto i = 0; i < m; ++i)
    {
        for (auto j = 0; j < n; ++j)
            std::cout << a[i][j] << " ";
        std::cout << std::endl;
    }
    std::cout << std::endl;
}

void test_fill_shape()
{
    char a[5][5] = 
    {   
    { 'X', 'X', 'X', 'X', 'X' },
    { 'X', 'X', 'O', 'O', 'X' },
    { 'X', 'X', 'O', 'O', 'X' },
    { 'X', 'X', 'X', 'X', 'X' },
    { 'O', 'X', 'X', 'X', 'X' } };
    char* ap[5] = { a[0], a[1], a[2], a[3], a[4] };
    fill_shape(ap, 5, 5);
    print_matrix(ap, 5, 5);
    char b[5][5] =
    { 
    { 'X', 'X', 'X', 'X', 'X' },
    { 'X', 'X', 'O', 'O', 'X' },
    { 'X', 'X', 'O', 'O', 'O' },
    { 'X', 'X', 'X', 'X', 'X' },
    { 'O', 'X', 'X', 'X', 'X' } };
    char* bp[5] = { b[0], b[1], b[2], b[3], b[4] };
    fill_shape(bp, 5, 5);
    print_matrix(bp, 5, 5);
    char c[5][6] =
    {
    { 'X', 'O', 'X', 'X', 'X', 'X' },
    { 'X', 'X', 'O', 'O', 'X', 'X' },
    { 'X', 'X', 'O', 'O', 'X', 'O' },
    { 'X', 'O', 'X', 'O', 'X', 'O' },
    { 'O', 'X', 'X', 'X', 'X', 'X' } };
    char* cp[5] = { c[0], c[1], c[2], c[3], c[4] };
    fill_shape(cp, 5, 6);
    print_matrix(cp, 5, 6);
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

bool replaceWithAndCheck(char replace, char fillchar, char **grid, int posy, int posx, int sizey, int sizex)
{
  if(posy<0 || posx<0 || posy>=sizey || posx>=sizex)
  {
    return false;
  }
  
  char *line=grid[posy];
  if(line[posx]!=replace)
  {
    return true;
  }
  
  line[posx]=fillchar;
  
  if(!replaceWithAndCheck(replace,fillchar,grid,posy,posx+1,sizey,sizex)) return false;
  if(!replaceWithAndCheck(replace,fillchar,grid,posy,posx-1,sizey,sizex)) return false;
  if(!replaceWithAndCheck(replace,fillchar,grid,posy+1,posx,sizey,sizex)) return false;
  return replaceWithAndCheck(replace,fillchar,grid,posy-1,posx,sizey,sizex);
}


void enclose_grid(char **grid, int sizey, int sizex)
{
  for(int y=1; y<sizey; y++)
  {
    for(int x=1; x<sizex; x++)
    {
      char *line=grid[y];
      if(line[x]=='O')
      {
        //Found a gap
        //printf("(%d,%d)\n",x,y);
        char *lineprevious=grid[y-1];
        if(line[x-1]=='X' && lineprevious[x]=='X')
        {
          //Ok, we are enclosed to the left and above
          //If it had been a O then we know that there is no
          //way it this spot can be enclosed, as it would already
          //have been filled.
                    
          bool result = replaceWithAndCheck('O','T',grid,y,x+1,sizey,sizex);
          //printf("res=%d\n",result);
          
          //It worked, so turn the Ts to Xs
          if(result)
            replaceWithAndCheck('T','X',grid,y,x,sizey,sizex);          
        }
      }
    }
  }
  //Finally, turn all the remaining Ts back to Os
  for(int y=0; y<sizey; y++)
  {
    for(int x=0; x<sizex; x++)
    {
      char *line=grid[y];
      if(line[x]=='T')
      {
        line[x]='O';
      }
    }
  }
  
  return;
  
}

void print_grid(char **grid, int sizey, int sizex)
{
  for(int y=0; y<sizey; y++)
  {
    printf("%s\n", grid[y]);
  }
  printf("\n");
}


int main(void)
{
  char **grid = new char*[12]();
  for(int x=0; x<12;x++)
  {
    grid[x] = new char[8]();
  }
  strcpy(grid[0],"XXXXXXOX");
  strcpy(grid[1],"XXOOXXOX");
  strcpy(grid[2],"OOXXXXOX");
  strcpy(grid[3],"XXOOXXXX");
  strcpy(grid[4],"XXOXXXOO");
  strcpy(grid[5],"XXXOOOXX");
  strcpy(grid[6],"XXXXXOXX");
  strcpy(grid[7],"XOOOXOXX");
  strcpy(grid[8],"XXXXXOXX");
  strcpy(grid[9],"XXOOOOXX");
  strcpy(grid[10],"XXXXXXXX");
  strcpy(grid[11],"XXXOXXXX");

  print_grid(grid,12,8);
  enclose_grid(grid,12,8);
  print_grid(grid,12,8);
}