Booking.com Interview Question Software Developers
Country: Netherlands
Interview Type: In-Person
www(dot)repl(dot)it/Klkv/4
import Data.Set (Set)
import qualified Data.Set as Set
-- defining our ADTs & getState signature. also, `Word` is unsigned int32
data State = B | W | E | O deriving (Show, Eq)
data Cord = Cord { x :: Word, y :: Word } deriving (Show, Eq, Ord)
-- getState is a provided function that translates cordination into its state
getState :: Cord -> State
-- and here's where the magic happens (isCaptured is our public API)
isCaptured :: Cord -> Bool
isCaptured cord = selfState `notElem` [O, E] && (isOccupied selfState $ getStates cord Set.empty)
where selfState = getState cord
surrounding :: Cord -> [Cord]
surrounding (Cord x y) = [Cord (x - 1) y, Cord (x + 1) y, Cord x (y - 1), Cord x (y + 1)]
getStates :: Cord -> Set Cord -> [State]
getStates self visited = cords >>= (\c -> if getState self == getState c then getStates c (Set.insert self visited) else [getState c])
where cords = filter (`Set.notMember` visited) $ surrounding self
isOccupied :: State -> [State] -> Bool
isOccupied _ [] = False
isOccupied x xs = all (`notElem` [E, x]) xs
-- sample data
getState (Cord 1 1) = B
getState (Cord 2 1) = W
getState (Cord 1 2) = W
getState (Cord 4 3) = B
getState (Cord 7 3) = W
getState (Cord 8 2) = W
getState (Cord 8 3) = B
getState (Cord 8 4) = W
getState (Cord 13 2) = W
getState (Cord 13 3) = W
getState (Cord 13 4) = W
getState (Cord 14 1) = W
getState (Cord 14 2) = B
getState (Cord 14 3) = B
getState (Cord 14 4) = B
getState (Cord 14 5) = W
getState (Cord 15 2) = W
getState (Cord 15 3) = W
getState (Cord 15 4) = W
-- defining defaults and setting a 50x50 board
getState (Cord x y)
| x <= 0 || y <= 0 = O
| x > 50 || y > 50 = O
| otherwise = E
-- and checking if anything here actually works
main :: IO()
main = print [isCaptured $ Cord 1 1, isCaptured $ Cord 4 3, isCaptured $ Cord 8 3, isCaptured $ Cord 14 2]
class Matrix<T> : IEnumerable<T[]>
{
private int rowsCount;
private int colsCount;
private T[][] data;
private int addIndex = 0;
public Matrix(int rowsCount, int colsCount)
{
this.rowsCount = rowsCount;
this.colsCount = colsCount;
this.data = new T[rowsCount][];
for (int i = 0; i < this.rowsCount; i++)
{
this.data[i] = new T[colsCount];
}
}
public T[] this[int row]
{
get
{
return this.data[row];
}
}
public void Add(params T[] columns)
{
if (this.addIndex == this.rowsCount)
{
return;
}
this.data[addIndex++] = columns;
}
public IEnumerator<T[]> GetEnumerator()
{
foreach (var item in this.data)
{
yield return item;
}
}
IEnumerator IEnumerable.GetEnumerator()
{
foreach (var item in this.data)
{
yield return item;
}
}
public int NumRows { get { return this.rowsCount; } }
public int NumCols { get { return this.colsCount; } }
}
class Program
{
static void Main(string[] args)
{
var n = 5;
var mat = new Matrix<char>(n, n)
{
{'E','E','E','E','E'},
{'E','W','W','W','E'},
{'W','B','B','B','W'},
{'E','W','W','W','E'},
{'E','E','E','E','E'}
};
var visited = new Matrix<bool>(n, n);
var isCaptured = FindIsCaptured(mat, visited, 2, 3);
Console.WriteLine(isCaptured);
}
private static bool FindIsCaptured(Matrix<char> mat, Matrix<bool> visited, int row, int column)
{
if (visited[row][column])
{
return true;
}
visited[row][column] = true;
if (mat[row][column] == 'E')
{
return false;
}
var isOOB = IsRowColumPairOutofBound(mat, row, column);
if (isOOB) return true;
var topCoords = Tuple.Create(row - 1, column);
var bottomCoords = Tuple.Create(row + 1, column);
var leftCoords = Tuple.Create(row, column - 1);
var rightCoords = Tuple.Create(row, column + 1);
var isTopOOB = IsRowColumPairOutofBound(mat, topCoords.Item1, topCoords.Item2);
var isBottomOOB = IsRowColumPairOutofBound(mat, bottomCoords.Item1, bottomCoords.Item2);
var isLeftOOB = IsRowColumPairOutofBound(mat, leftCoords.Item1, leftCoords.Item2);
var isRightOOB = IsRowColumPairOutofBound(mat, rightCoords.Item1, rightCoords.Item2);
var isTopCaptured = isTopOOB || (mat[topCoords.Item1][topCoords.Item2] != 'E' && mat[topCoords.Item1][topCoords.Item2] != mat[row][column]) || FindIsCaptured(mat, visited, topCoords.Item1, topCoords.Item2);
var isBottomCaptured = isBottomOOB || (mat[bottomCoords.Item1][bottomCoords.Item2] != 'E' && mat[bottomCoords.Item1][bottomCoords.Item2] != mat[row][column]) || FindIsCaptured(mat, visited, bottomCoords.Item1, bottomCoords.Item2);
var isLeftCaptured = isLeftOOB || (mat[leftCoords.Item1][leftCoords.Item2] != 'E' && mat[leftCoords.Item1][leftCoords.Item2] != mat[row][column]) || FindIsCaptured(mat, visited, leftCoords.Item1, leftCoords.Item2);
var isRightCaptured = isRightOOB || (mat[rightCoords.Item1][rightCoords.Item2] != 'E' && mat[rightCoords.Item1][rightCoords.Item2] != mat[row][column]) || FindIsCaptured(mat, visited, rightCoords.Item1, rightCoords.Item2);
return isTopCaptured && isBottomCaptured && isLeftCaptured && isRightCaptured;
}
private static bool IsRowColumPairOutofBound(Matrix<char> mat, int row, int column)
{
if (row < 0)
{
return true;
}
if (row >= mat.NumRows)
{
return true;
}
if (column < 0)
{
return true;
}
if (column >= mat.NumCols)
{
return true;
}
return false;
}
}
Sorry if I misunderstood, the question, it seems fairly straight forward from description, here is some pseudo code
bool IsCaptured(int x, int y) {
if(x < 0 || y <0 || x >= state.GetLength(0) || y >= state.GetLength(1))
{
return false;
}
// or single cell
return true
var currentState = state[x,y];
if(x -1 >=0 && state[x-1, y] == currentState or empty){ return false;}
if(y -1 >=0 && state[x, y-1] == currentState or empty){ return false;}
if(x + 1 < state.GetLength(0) && state[x + 1, y] == currentState or empty){ return false;}
if(y + 1 < state.GetLength(1) && state[x, y + 1] == currentState or empty){ return false;}
}
@johanson1, thanks for pointing out what I missed (if cell neighboring has like wise state, my code has to check it is not captured as well which is recursive in nature), sorry for my incorrect answer, I will try out dp approach with some memorization to solve it, thinking about it see O(n^2), but may be I am wrong, I will try to work it out, thanks again
class Matrix<T> : IEnumerable<T[]>
{
private int rowsCount;
private int colsCount;
private T[][] data;
private int addIndex = 0;
public Matrix(int rowsCount, int colsCount)
{
this.rowsCount = rowsCount;
this.colsCount = colsCount;
this.data = new T[rowsCount][];
for (int i = 0; i < this.rowsCount; i++)
{
this.data[i] = new T[colsCount];
}
}
public T[] this[int row]
{
get
{
return this.data[row];
}
}
public void Add(params T[] columns)
{
if (this.addIndex == this.rowsCount)
{
return;
}
this.data[addIndex++] = columns;
}
public IEnumerator<T[]> GetEnumerator()
{
foreach (var item in this.data)
{
yield return item;
}
}
IEnumerator IEnumerable.GetEnumerator()
{
foreach (var item in this.data)
{
yield return item;
}
}
public int NumRows { get { return this.rowsCount; } }
public int NumCols { get { return this.colsCount; } }
}
class Program
{
static void Main(string[] args)
{
var n = 5;
var mat = new Matrix<char>(n, n)
{
{'E','E','E','E','E'},
{'E','W','W','W','E'},
{'W','B','B','B','W'},
{'E','W','W','W','E'},
{'E','E','E','E','E'}
};
var visited = new Matrix<bool>(n, n);
var isCaptured = FindIsCaptured(mat, visited, 2, 3);
Console.WriteLine(isCaptured);
}
private static bool FindIsCaptured(Matrix<char> mat, Matrix<bool> visited, int row, int column)
{
if (visited[row][column])
{
return true;
}
visited[row][column] = true;
if (mat[row][column] == 'E')
{
return false;
}
var isOOB = IsRowColumPairOutofBound(mat, row, column);
if (isOOB) return true;
var topCoords = Tuple.Create(row - 1, column);
var bottomCoords = Tuple.Create(row + 1, column);
var leftCoords = Tuple.Create(row, column - 1);
var rightCoords = Tuple.Create(row, column + 1);
var isTopOOB = IsRowColumPairOutofBound(mat, topCoords.Item1, topCoords.Item2);
var isBottomOOB = IsRowColumPairOutofBound(mat, bottomCoords.Item1, bottomCoords.Item2);
var isLeftOOB = IsRowColumPairOutofBound(mat, leftCoords.Item1, leftCoords.Item2);
var isRightOOB = IsRowColumPairOutofBound(mat, rightCoords.Item1, rightCoords.Item2);
var isTopCaptured = isTopOOB || (mat[topCoords.Item1][topCoords.Item2] != 'E' && mat[topCoords.Item1][topCoords.Item2] != mat[row][column]) || FindIsCaptured(mat, visited, topCoords.Item1, topCoords.Item2);
var isBottomCaptured = isBottomOOB || (mat[bottomCoords.Item1][bottomCoords.Item2] != 'E' && mat[bottomCoords.Item1][bottomCoords.Item2] != mat[row][column]) || FindIsCaptured(mat, visited, bottomCoords.Item1, bottomCoords.Item2);
var isLeftCaptured = isLeftOOB || (mat[leftCoords.Item1][leftCoords.Item2] != 'E' && mat[leftCoords.Item1][leftCoords.Item2] != mat[row][column]) || FindIsCaptured(mat, visited, leftCoords.Item1, leftCoords.Item2);
var isRightCaptured = isRightOOB || (mat[rightCoords.Item1][rightCoords.Item2] != 'E' && mat[rightCoords.Item1][rightCoords.Item2] != mat[row][column]) || FindIsCaptured(mat, visited, rightCoords.Item1, rightCoords.Item2);
return isTopCaptured && isBottomCaptured && isLeftCaptured && isRightCaptured;
}
private static bool IsRowColumPairOutofBound(Matrix<char> mat, int row, int column)
{
if (row < 0)
{
return true;
}
if (row >= mat.NumRows)
{
return true;
}
if (column < 0)
{
return true;
}
if (column >= mat.NumCols)
{
return true;
}
return false;
}
}
#include "stdafx.h"
#include <assert.h>
using namespace std;
typedef enum
{
BLACK = 0,
WHITE,
OUT_OF_BOUNDS,
EMPTY
} STATE;
class Board
{
public:
Board()
{
board = nullptr;
checked = nullptr;
};
~Board()
{
if (board != nullptr)
{
delete board;
board = nullptr;
}
if (checked != nullptr)
{
delete checked;
checked = nullptr;
}
}
STATE getState(int x, int y)
{
int coord = (x - 1)*N + (y - 1);
if (x < 1 || y < 1 || x > N || y > N || coord > N*N)
return OUT_OF_BOUNDS;
return board[coord];
}
void setState(int x, int y, STATE s)
{
int coord = (x - 1)*N + (y - 1);
assert(coord < N*N);
board[coord] = s;
}
void init(int n)
{
N = n;
if (board != nullptr)
{
delete board;
board = nullptr;
}
if (checked != nullptr)
{
delete checked;
checked = nullptr;
}
assert(N >= 1);
board = new STATE[N*N];
checked = new bool[N*N];
for (int x = 1; x <= N; x++)
{
for (int y = 1; y <= N; y++)
{
setState(x, y, EMPTY);
}
}
}
bool isCaptured(int x, int y)
{
memset(checked, false, N*N*sizeof(bool));
bool ret = isCaptured(x, y, checked);
return ret;
}
private:
bool isCaptured(int x, int y, bool* checked)
{
STATE thisState = getState(x, y);
switch (thisState)
{
case WHITE:
case BLACK:
{
// return true if one adjacent is empty
// or if one adjacent 'same color' is not captured
STATE sT = getState(x-1 , y );
STATE sR = getState(x , y+1 );
STATE sL = getState(x , y-1 );
STATE sB = getState(x+1 , y );
if (sT == EMPTY ||
sR == EMPTY ||
sL == EMPTY ||
sB == EMPTY
)
return false;
assert((x-1)*N + (y-1) < N*N);
// mark this as checked so that we don't enter an infinite loop when testing for a neighbour
checked[(x-1)*N + (y-1)] = true;
if (sT == thisState && checked[(x-2) * N + (y-1)] == false && !isCaptured(x-1, y, checked))
return false;
if (sR == thisState && checked[(x-1) * N + y] == false && !isCaptured(x, y+1, checked))
return false;
if (sL == thisState && checked[(x-1) * N + (y-2)] == false && !isCaptured(x, y-1, checked))
return false;
if (sB == thisState && checked[x*N + (y-1)] == false && !isCaptured(x+1, y, checked))
return false;
return true;
}
break;
default:
break;
}
return false;
}
private:
int N;
STATE* board;
bool* checked;
};
void runAllTests()
{
// 1.
{
Board b;
b.init(1);
assert(b.getState(1, 1) == EMPTY);
}
// 2.
{
Board b;
b.init(2); // 2x2, all black
for (int i = 1; i <= 2; i++)
{
for (int j = 1; j <= 2; j++)
{
b.setState(i, j, BLACK);
}
}
assert(b.getState(1, 1) == BLACK);
}
// 3.
{
Board b;
b.init(3);
for (int i = 1; i <= 3; i++)
{
for (int j = 1; j <= 3; j++)
{
b.setState(i, j, BLACK);
}
}
b.setState(2, 2, WHITE);
assert(b.isCaptured(2, 2) == true);
}
// 4.
{
Board b;
b.init(3);
for (int i = 1; i <= 3; i++)
{
for (int j = 1; j <= 3; j++)
{
b.setState(i, j, BLACK);
}
}
b.setState(2, 2, WHITE);
b.setState(2, 3, WHITE);
assert(b.isCaptured(2, 2) == true);
}
// 5
{
Board b;
b.init(2);
b.setState(1, 1, BLACK);
b.setState(1, 2, WHITE);
b.setState(2, 1, WHITE);
assert(b.isCaptured(1, 1) == true);
}
// 6
{
Board b;
b.init(5);
b.setState(2, 2, WHITE);
b.setState(2, 3, WHITE);
b.setState(2, 4, WHITE);
b.setState(3, 1, WHITE);
b.setState(3, 2, BLACK);
b.setState(3, 3, BLACK);
b.setState(3, 4, BLACK);
b.setState(4, 2, WHITE);
b.setState(4, 3, WHITE);
//b.setState(4, 4, WHITE);
assert(b.isCaptured(3, 2) == false);
assert(b.isCaptured(3, 3) == false);
}
}
int main()
{
runAllTests();
return 0;
}
package com.company;
import java.util.HashSet;
import java.util.Set;
public class BoardGame {
// 1 - white
//2 - black
//0 - empty
//-1 out of boarder
private int[][] board;
int size;
private Set<String> examined = new HashSet<>();
public BoardGame(int size) {
this.size = size;
board = new int[size][size];
}
public boolean addWhite(int x, int y) {
if (x - 1 >= size || y - 1 >= size) {
return false;
}
board[y - 1][x - 1] = 1;
return true;
}
public boolean addBlack(int x, int y) {
if (x - 1 >= size || y - 1 >= size) {
return false;
}
board[y - 1][x - 1] = 2;
return true;
}
public boolean isBlocked(int x, int y) {
if (x - 1 >= size || y - 1 >= size) {
return false;
}
int current = getState(x, y);
if (current == 0) {
return false;
}
int opponent = current == 1 ? 0 : 1;
boolean lblocked =
getState(x - 1, y) == opponent || getState(x - 1, y) == -1 || (getState(x - 1, y) == current
&& neighbour(x - 1, y));
boolean rblocked =
getState(x + 1, y) == opponent || getState(x + 1, y) == -1 || (getState(x + 1, y) == current
&& neighbour(x + 1, y));
boolean ublocked =
getState(x, y + 1) == opponent || getState(x, y + 1) == -1 || (getState(x, y + 1) == current
&& neighbour(x, y + 1));
boolean dblocked =
getState(x, y - 1) == opponent || getState(x, y - 1) == -1 || (getState(x, y - 1) == current
&& neighbour(x, y - 1));
return lblocked && rblocked && ublocked && dblocked;
}
private boolean neighbour(int x, int y) {
if (examined.contains(x + ":" + y)) {
return true;
}
examined.add(x + ":" + y);
return isBlocked(x, y);
}
public int getState(int x, int y) {
if (x - 1 >= size || y - 1 >= size) {
return -1;
}
if (x - 1 < 0 || y - 1 < 0) {
return -1;
}
return board[y - 1][x - 1];
}
public static void main(String[] args) {
BoardGame boardGame = new BoardGame(2);
boardGame.addBlack(1, 1);
boardGame.addWhite(1, 2);
boardGame.addWhite(2, 1);
System.out.printf(String.valueOf(boardGame.isBlocked(1, 1)));
boardGame = new BoardGame(5);
boardGame.addWhite(2, 2);
boardGame.addWhite(2, 3);
boardGame.addWhite(3, 1);
boardGame.addWhite(3, 4);
boardGame.addWhite(4, 2);
boardGame.addWhite(4, 3);
boardGame.addBlack(3, 2);
boardGame.addBlack(3, 3);
System.out.printf(String.valueOf(boardGame.isBlocked(3, 2)));
}
}
public static boolean isTrapped(char[][] arr, int i, int j, int m, int n , boolean[][] visited) {
int[] xAxis = {-1,0,1,0};
int[] yAxis = {0,1,0,-1};
char sourceChar = arr[i][j];
visited[i][j] = true;
for (int k = 0; k < yAxis.length; k++) {
int x = i + xAxis[k];
int y = j + yAxis[k];
if(isValidMove(arr, x, y, m, n) && !visited[x][y]) {
if(arr[x][y] == sourceChar) {
boolean result = isTrapped(arr, x, y, m, n, visited);
if(result) {
return true;
}
}else if(arr[x][y] == ' ') {
return true;
}
}
}
return false;
}
private static boolean isValidMove(char[][] arr, int x, int y, int m, int n) {
return x >= 0 && y>=0 && x < m && y < n ;
}
enum square_state
{
BLACK,
WHITE,
EMPTY,
OUT_OF_BOUND
};
// Suppose board and visited are filled.
vector<vector<square_state>> board;
vector<vector<bool>> visited;
square_state getState(int x, int y)
{
if (x < 0 || x > 3 || y < 0 || y > 3)
return OUT_OF_BOUND;
return board[x][y];
}
bool is_captured(int x, int y)
{
queue<pair<int, int>> q;
q.emplace(x, y);
while (!q.empty())
{
auto cur_cell = q.front();
auto cur_cell_state = getState(cur_cell.first, cur_cell.second);
q.pop();
if (cur_cell_state == EMPTY || cur_cell_state == OUT_OF_BOUND)
return false;
auto up_cell = make_pair(cur_cell.first, cur_cell.second - 1);
auto up_cell_state = getState(up_cell.first, up_cell.second);
if (up_cell_state == EMPTY)
return false;
if (!visited[up_cell.first][up_cell.second] && cur_cell_state == up_cell_state)
q.emplace(up_cell);
auto down_cell = make_pair(cur_cell.first, cur_cell.second + 1);
auto down_cell_state = getState(down_cell.first, down_cell.second);
if (down_cell_state == EMPTY)
return false;
if (!visited[down_cell.first][down_cell.second] && cur_cell_state == down_cell_state)
q.emplace(down_cell);
auto left_cell = make_pair(cur_cell.first - 1, cur_cell.second);
auto left_cell_state = getState(left_cell.first, left_cell.second);
if (left_cell_state == EMPTY)
return false;
if (!visited[left_cell.first][left_cell.second] && cur_cell_state == left_cell_state)
q.emplace(left_cell);
auto right_cell = make_pair(cur_cell.first + 1, cur_cell.second);
auto right_cell_state = getState(right_cell.first, right_cell.second);
if (right_cell_state == EMPTY)
return false;
if (!visited[right_cell.first][right_cell.second] && cur_cell_state == right_cell_state)
q.emplace(right_cell);
visited[cur_cell.first][cur_cell.second] = true;
}
return true;
}
Java solution with BFS
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
public class GoGame {
public static boolean isSurrounded(int x, int y, char[][] board){
int[] root = new int[]{x-1,y-1};
char color = board[x-1][y-1];
List<int[]> queue = new ArrayList<int[]>();
queue.add(root);
int[][] visited = new int[board.length][board[0].length];
while(!queue.isEmpty()){
int[] cell = queue.remove(0);
int cellX = cell[0];
int cellY = cell[1];
if(visited[cellX][cellY]==1){
continue;
}
visited[cellX][cellY] = 1;
char cellColor = board[cellX][cellY];
if(isEmptyCell(cellColor)){
return false;
}
if(isSameColor(color, cellColor)){
List<int[]> neighbours = getNeighbours(cellX,cellY,board);
for(int i=0; i<neighbours.size();i++){
queue.add(neighbours.get(i));
}
}
}
return true;
}
private static List<int[]> getNeighbours(int x, int y, char[][] board){
List<int[]> neighbours = new ArrayList<int[]>();
int[][] offset = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
for(int i=0; i<offset.length; i++){
int neighbourX = x + offset[i][0];
int neighbourY = y + offset[i][1];
if(neighbourX < 0 ||
neighbourY < 0 ||
neighbourX >= board.length ||
neighbourY >= board[0].length
){
continue;
}
neighbours.add(new int[]{neighbourX,neighbourY});
}
return neighbours;
}
private static boolean isEmptyCell(char cell){
return cell == 'E';
}
private static boolean isSameColor(char cell1, char cell2){
return cell1 == cell2;
}
public static void main(String[] args){
char[][] board = new char[][]{
{'E','W','W','W','W','W','W'},
{'E','W','B','W','W','W','W'},
{'E','W','B','W','W','B','W'},
{'E','W','B','B','W','B','B'},
{'E','W','W','B','B','W','W'},
{'E','B','B','B','W','W','W'},
{'E','W','W','W','B','W','W'},
{'E','W','W','W','W','W','W'}
};
System.out.println(GoGame.isSurrounded(1,3,board));
System.out.println(GoGame.isSurrounded(4,4,board));
System.out.println(GoGame.isSurrounded(7,5,board));
System.out.println(GoGame.isSurrounded(4,6,board));
}
}
Java solution with BFS
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;
public class GoGame {
public static boolean isSurrounded(int x, int y, char[][] board){
int[] root = new int[]{x-1,y-1};
char color = board[x-1][y-1];
List<int[]> queue = new ArrayList<int[]>();
queue.add(root);
int[][] visited = new int[board.length][board[0].length];
while(!queue.isEmpty()){
int[] cell = queue.remove(0);
int cellX = cell[0];
int cellY = cell[1];
if(visited[cellX][cellY]==1){
continue;
}
visited[cellX][cellY] = 1;
char cellColor = board[cellX][cellY];
if(isEmptyCell(cellColor)){
return false;
}
if(isSameColor(color, cellColor)){
List<int[]> neighbours = getNeighbours(cellX,cellY,board);
for(int i=0; i<neighbours.size();i++){
queue.add(neighbours.get(i));
}
}
}
return true;
}
private static List<int[]> getNeighbours(int x, int y, char[][] board){
List<int[]> neighbours = new ArrayList<int[]>();
int[][] offset = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
for(int i=0; i<offset.length; i++){
int neighbourX = x + offset[i][0];
int neighbourY = y + offset[i][1];
if(neighbourX < 0 ||
neighbourY < 0 ||
neighbourX >= board.length ||
neighbourY >= board[0].length
){
continue;
}
neighbours.add(new int[]{neighbourX,neighbourY});
}
return neighbours;
}
private static boolean isEmptyCell(char cell){
return cell == 'E';
}
private static boolean isSameColor(char cell1, char cell2){
return cell1 == cell2;
}
public static void main(String[] args){
char[][] board = new char[][]{
{'E','W','W','W','W','W','W'},
{'E','W','B','W','W','W','W'},
{'E','W','B','W','W','B','W'},
{'E','W','B','B','W','B','B'},
{'E','W','W','B','B','W','W'},
{'E','B','B','B','W','W','W'},
{'E','W','W','W','B','W','W'},
{'E','W','W','W','W','W','W'}
};
System.out.println(GoGame.isSurrounded(1,3,board));
System.out.println(GoGame.isSurrounded(4,4,board));
System.out.println(GoGame.isSurrounded(7,5,board));
System.out.println(GoGame.isSurrounded(4,6,board));
}
}
/**
* @author Omid Ghiasi Tarzi
*/
static boolean isCaptured(int x,int y){
Set<String> indexes=new HashSet<>();
String currentState=getState(x,y);
return isCaptured(x,y,currentState,indexes);
}
static boolean isCaptured(int x, int y, String desired, Set<String> indexes){
String current=getState(x,y);
if(current.equals("empty")){
return false;
}
if(!current.equals(desired)){
return true;
}
String index=x+","+y;
if(indexes.contains(index)){
return true;
}
indexes.add(index);
return isCaptured(x-1,y,desired,indexes)&&
isCaptured(x+1,y,desired,indexes)&&
isCaptured(x,y-1,desired,indexes)&&
isCaptured(x,y+1,desired,indexes);
}
Solution in Python
{{
def _is_captured(base_color, r, c, R, C, arr, visited):
check_X_axis = [-1, 1, 0, 0]
check_Y_axis = [0, 0, -1, 1]
status = False
if visited[r][c] is True:
return False
visited[r][c] = True
for i in range(4):
l = check_X_axis[i]
m = check_Y_axis[i]
if r+l < R and r+l >= 0 and c+m < C and c+m >= 0:
if arr[r+l][c+m] == "E":
status = True
elif base_color != arr[r+l][c+m]:
status = False
else:
status = _is_captured(base_color, r+l, c+m, R, C, arr, visited)
if status:
return True
return False
def is_captured(r, c, arr):
R = len(arr)
C = len(arr[0])
visited = [[False]*C for r in range(R)]
color = arr[r][c]
return _is_captured(color, r , c, R, C, arr, visited)
arr = [["E", "W", "W", "W", "E"],
["W", "B", "B", "B", "W"],
["E", "W", "W", "W", "E"]]
is_captured(1, 2, arr)
}}
{{def _is_captured(base_color, r, c, R, C, arr, visited):
check_X_axis = [-1, 1, 0, 0]
check_Y_axis = [0, 0, -1, 1]
status = False
if visited[r][c] is True:
return False
visited[r][c] = True
for i in range(4):
l = check_X_axis[i]
m = check_Y_axis[i]
if r+l < R and r+l >= 0 and c+m < C and c+m >= 0:
if arr[r+l][c+m] == "E":
status = True
elif base_color != arr[r+l][c+m]:
status = False
else:
status = _is_captured(base_color, r+l, c+m, R, C, arr, visited)
if status:
return True
return False
def is_captured(r, c, arr):
R = len(arr)
C = len(arr[0])
visited = [[False]*C for r in range(R)]
color = arr[r][c]
return _is_captured(color, r , c, R, C, arr, visited)
arr = [["E", "W", "W", "W", "E"],
["W", "B", "B", "B", "W"],
["E", "W", "W", "W", "E"]]
is_captured(1, 2, arr) }}
import java.util.LinkedList;
import java.util.Queue;
public class GoGame {
public static boolean isSurrounded(int x, int y, char[][] chars) {
if (!isValidLocation(chars, x, y) || chars[x][y] == 'E') {
return false;
}
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{x, y});
char sourceColoer = chars[x][y];
boolean[][] visited = new boolean[chars.length][chars[0].length];
while (!queue.isEmpty()) {
int[] location = queue.poll();
int curX = location[0], curY = location[1];
visited[curX][curY] = true;
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (int[] dir : dirs) {
int nextX = curX + dir[0], nextY = curY + dir[1];
if (isValidLocation(chars, nextX, nextY) && !visited[nextX][nextY]) {
if (chars[x][y] == 'E') {
return false;
} else if (chars[x][y] == sourceColoer) {
queue.offer(new int[]{nextX, nextY});
}
}
}
}
return true;
}
private static boolean isValidLocation(char[][] chars, int i, int j) {
if (i < 0 || j < 0 || i > chars.length - 1 || j > chars[0].length - 1) {
return false;
}
return true;
}
public static void main(String[] args){
char[][] board = new char[][]{
{'E','W','W','W','W','W','W'},
{'E','W','B','W','W','W','W'},
{'E','W','B','W','W','B','W'},
{'E','W','B','B','W','B','B'},
{'E','W','W','B','B','W','W'},
{'E','B','B','B','W','W','W'},
{'E','W','W','W','B','W','W'},
{'E','W','W','W','W','W','W'}
};
System.out.println(GoGame.isSurrounded(1,3,board));
System.out.println(GoGame.isSurrounded(4,4,board));
System.out.println(GoGame.isSurrounded(7,5,board));
System.out.println(GoGame.isSurrounded(4,6,board));
}
}
- LG February 03, 2019public static boolean isTrapped(char[][] arr, int i, int j, int m, int n , boolean[][] visited) { int[] xAxis = {-1,0,1,0}; int[] yAxis = {0,1,0,-1}; char sourceChar = arr[i][j]; visited[i][j] = true; for (int k = 0; k < yAxis.length; k++) { int x = i + xAxis[k]; int y = j + yAxis[k]; if(isValidMove(arr, x, y, m, n) && !visited[x][y]) { if(arr[x][y] == sourceChar) { boolean result = isTrapped(arr, x, y, m, n, visited); if(result) { return true; } }else if(arr[x][y] == ' ') { return true; } } } return false; } private static boolean isValidMove(char[][] arr, int x, int y, int m, int n) { return x >= 0 && y>=0 && x < m && y < n ; }