Google Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
Good idea, make it really simple
Only one thing, I think the third for loop should be: for (int i = 1; i < A.size()-1; i++)
since in the first and second loop, we have checked all the spots in the first and last line.
Wouldn't this fail for something 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
The answer should be unchanged, but your solution makes it:
X X X X X
X X X X X
X X X X X
X X X X X
O X X X X
Can the person who down voted provide some explanation? I believe the program posted will fail with my example. PLEASE PROVIDE EXPLANATION BEFORE DOWN VOTING!!!!
For ex following should not replace anything,
O X X X
X O O X
X O O X
X X X X
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
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);
}
- Westlake February 14, 2014