CareerCup

Just check the edges for no zeros. That's it

say matrix(n*m) is :
1 1 1 1 1 1
1 1 1 0 0 1
1 0 0 0 0 1
1 0 0 0 0 1
1 0 0 0 1 1
1 1 1 1 1 1

Algo :
1. create a temporary matrix by calculating the number of 1's a 0 is surrounded with:
T(n*m)
0 0 0 0 0 0
0 0 0 2 3 0
0 2 2 2 3 0
0 2 2 2 4 0
0 3 3 4 0 0
0 0 0 0 0 0

code:

Boolean hasIsland( int matrix[][]){
	int walls = 0;
	int temp[][] = {0}; 
	for(i = 0 ; i <n ; i++)
		for(j = 0 ; j < m ; j++ )
			if(matrix[i][j] == 0){
				fill(matrix, i , j , temp, n , m );
				if( temp[i][j] > walls )
					walls = temp[i][j];
			}

	if(walls == 4){
		system.out.print("has island");
		return true;
	}
}

void fill( int matrix[][], int i , int j , int temp[][], int n , int m ){

	temp[i][j] = 0;
	if( i == 0 || j == 0 || i == n-1 || j == m-1 ) return;
		
	if( matrix[i][j-1] == 1 || temp[i][j-1] > 0 )
		temp[i][j] += 1;

	if( matrix[i-1][j] == 1 || temp[i-1][j] > 0 )
		temp[i][j] += 1;

	if( matrix[i+][j] == 1 )
		temp[i][j] += 1;
	if( matrix[i][j+1] == 1 )
		temp[i][j] += 1;

	return;
}

Hmmm... the problem statement is odd. If it was truely go, and the full boolean matrix was actually full, then whoever placed the last piece captured the other set and the game is not over. For sake of argument I'm going to say that black placed the last piece.

Conversely, if the black blob surrounds any white pieces, it would capture *that* blob, and thus the game may not be over.

A black blob would be safe from capture if it has two eyes, that is, there are two captured single wide spots inside it. However, the game would still be "over" in that sense.

I suspect that the actual code would either have to be an enumerable state which could have a "no piece" state or a nullable boolean.

Do the edges not count as enclosed?

DFS would do.
1. Let's call a matrix visited, and another matrix success having same number of columns and rows as the board.
2. When we visit a cell on board, we mark it as true in visited.
3. Success is true incase the cell is surrounded by 1's.
4. Start from a cell which is 0 on board, if not visited. Visit it.
5. Visiting mean, marking it as true, and then recurring the same to all cells at one unit apart.
6. Now, dfs should always end( when there is no more unvisited neighbour) at a cell with value 1. If it does so mark it's success as true and return true.
7. For a 0 valued cell to have success true, all of it's neighbors should return true.
8. Incase a cell is already visited, return it's success value.

Assuming we are given the coordinates of the 0 that may be surrounded. Otherwise, we would check every single 0, keeping track of the 0s that have already been checked.

def island_of_0s_is_completely_surrounded_by_1s(bool_m, row_of_0, col_of_0):
    unexplored = [(row_of_0, col_of_0)]
    visited = []
    for row in bool_m:
        visited.append([0] * len(bool_m[0]))

    while unexplored:
        cur_row, cur_col = unexplored.pop()
        if bool_m[cur_row][cur_col] == None:
            return False
        visited.append((cur_row, cur_col))
        append_if_valid(cur_row-1, cur_col, unexplored, bool_m)
        append_if_valid(cur_row, cur_col-1, unexplored, bool_m)
        append_if_valid(cur_row+1, cur_col, unexplored, bool_m)
        append_if_valid(cur_row, cur_col+1, unexplored, bool_m)
    return True


def append_if_valid(row, col, candidates_to_explore, matrix):
    if (row, col) not in candidates_to_explore and row >= 0 and col >=0 and row < len(matrix) and col < len(matrix[0]):
        if matrix[row][col] != 1:
            candidates_to_explore.append((row, col))

print island_of_0s_is_completely_surrounded_by_1s([[1, 1, 1], [1, None, 0]], 1, 2)

bool go_check(vector<vector<bool>> &matrix){
    int m=matrix.size(), n=matrix[0].size();
    vector<pair<int,int>> store;
    for(int i=0; i<m; ++i){
        if(!matrix[i][0])
            store.push_back(make_pair(i,0));
        if(!matrix[i][n-1])
            store.push_back(make_pair(i,n-1));
    }
    for(int j=0; j<n; ++j){
        if(!matrix[0][j])
            store.push_back(make_pair(0,j));
        if(!matrix[m-1][j])
            store.push_back(make_pair(m-1,j));
    }
    if(store.empty())
        return true;
    vector<vector<bool>> visited(m, vector<bool>(n,0));
    function<void(int,int)> fun=[&](int i, int j){
        if(i<0 || i>=m || j<0 || j>=n || visited[i][j] || matrix[i][j])
            return;
        visited[i][j]=true;
        if((i==0 || i==m-1) && (j==0 || j==n-1))
            return;
        fun(i-1,j);
        fun(i+1,j);
        fun(i,j-1);
        fun(i,j+1);
    };
    for_each(store.begin(), store.end(), [&fun](pair<int,int> p){ fun(p.first, p.second); });
    for(int i=0; i<m; ++i)
        for(int j=0; j<n; ++j)
            if(!visited[i][j] && !matrix[i][j])
                return true;
    return false;
}

// Note that I have switched zeros and 1s

public class MatrixProblem {
	/**
	 * Design an algo to decide if the GO game is over. i.e. 
	 * Given a boolean matrix, write a code to find if an island of 1's is completely surrounded by 0's.
	 * @param a
	 * @return
	 */
	public static boolean IsGoGameOver(int [][] a)
	{
	    if (a == null)
	    {
	        throw new RuntimeException("a");
	    }
	    
	    if (a.length == 0 || a[0].length == 0)
	    {
	        System.out.println("Array length is zero");
	        return false;
	    }
	    
	    // The boolean 2D array is initialized to false
	    boolean [][]visited = new boolean[a.length][a[0].length];
	    
	    for (int i = 0; i < a.length; i++)
	    {
	        for (int j = 0; j < a[0].length; j++)
	        {
	            if (a[i][j] == 1 && !visited[i][j])
	            {
	                if (IdentifyIsland(a, i, j, visited))
	                {
	                    return true;
	                }
	            }
	        }
	    }
	    
	    return false;
	}

	/**
	 * Actual logic to find if the island is surrounded with 0
	 * @param a
	 * @param row
	 * @param col
	 * @param visited
	 * @return
	 */
	private static boolean IdentifyIsland(int[][] a, int row, int col, boolean[][] visited)
	{
	    // No checks will be performed since this is an private class.

	    visited[row][col] = true;
	    if (row == 0 || row == a.length - 1 || col == 0 || col == a[0].length - 1) {
	    	visited[row][col] = false;
	    	return false;
	    }
	    
	    boolean up = true;
	    boolean down = true;
	    boolean left = true;
	    boolean right  = true;
	    if (a[row - 1][col] == 1 && !visited[row - 1][col]) up = IdentifyIsland (a, row - 1, col, visited);
	    if (a[row][col + 1] == 1 && !visited[row][col+1]) right = IdentifyIsland (a, row, col + 1, visited); 
	    if (a[row + 1][col] == 1 && !visited[row + 1][col]) down = IdentifyIsland (a, row + 1, col, visited); 
	    if (a[row][col - 1] == 1 && !visited[row][col - 1]) left = IdentifyIsland (a, row, col - 1, visited); 
	    return up && right && down && left;
	}
}

trap problem

// if we don't care how many island in the matrix
// if there's no 0 on the matrix's border, it would be OK

is0surrounded = true;

for(size_t i = 0;i<n;i++){
	if( map[i][0] || map[i][m-1] ){
		is0surrounded = true;
		break;
	}
}

for(size_t j = 0;j<m;j++){
	if(map[0][j] || map[n-1][j]){
		is0surrounded = true;
		break;
	}
}

// if there must be one island and it must be surrounded by 1

boolean map[][];
int directions[4][2] = {
	{ 0, 1},
	{ 0,-1},
	{ 1, 0},
	{-1, 0},
};

bool isBoundaryPosition(int i, int j)
{
	if( i == 0 || j == 0 || i == n-1 || j == m-1 )
		return true;
	return false;
}

pair<int, int> go(pair<int, int> p, int direction[]){
	return make_pair<int, int> (p.first+direction[0], p.second+direction[1] );
}

bool breath_search_surround_island(int i, int j)
{
	queue< pair<int,int> > que;
	map[i][j] = 1;
	if ( isBoundaryPosition(i,j) ){
		return false;
	}

	que.push( make_pair<int,int>(i,j) );
	while( !que.empty() ){
		pair<int, int> p = que.pop();
		for(size_t di = 0; di<4; di++){
			var pgo = go(p, directions[di]);
			if( map[pgo.first][pgo.second] )
				continue;
			if( isBoundaryPosition(pgo) )
				return false;
			map[pgo.first][pgo.second] = true;
			que.push( pgo );
		}
	}
	return true;
}

is0surrounded = true;  //whether is all 0 surrounded by 1
zero_island_count = 0; //how many islands;  if not all 0 is surrounded, this number is not accurate.
for(size_t i = 0; i<n && !is0surrounded; i++){
	for(size_t j = 0; j<m && !is0surrounded; j++){
		if(map[i][j] == 0){
			if( breath_search_surround_island(i, j) )
				zero_island_count++;
			else
				is0surrounded = false;
		}
	}
}
if( is0surrounded && zero_island_count==0)// there is no islands
	is0surrounded = false;

What I propose is to find connected components of "0s". If some connected component does not touch a border of a game board the game is over:
1) Go through "0"s on the board and recursively visit all neighbour "0s" by depth-first-search. When visiting a "0" mark it as visited in auxiliary array.
2) Keep track of whether all visited "0"s in one connected component are inside the board (not touching the border).
This solution shoult be O(MN) in time and space.

public class GO {
  private boolean[][] marked;
  private boolean[][] board;
  private int M,N;
  // Find conected component on unmarked “0” and
  // check if the component touches a border of the board.
  public isGamveOver(boolean[][] board) {
      this.M = board.length; 
      this.N = board[0].length;
      this.board = board;
      marked = new boolean[M][N];
      for (int k=0; k<M*N; k++)         // init as false
          marked[k/M][k%N] = false;

      for (int k=0; k<M*N; k++) {
          int i = k/M,   j=k%N;
          if (isValid(i, j) && !marked[i][j]) {
              boolean isOver = dfs(i, j);
              if (isOver)    
                  return true;
          }
    }
     return false;
  }
  // DFS - recursively mark connected component (CC)
  private boolean dfs(int i, int j) {
        marked[i][j] = true;
        boolean out = !isBorder(i,j);
        // Check 8 neighbours, if CC hits the border
        // out turns to “false”;
        for (int ii = i-1; ii<=i+1; ii++)     
            for (int jj = j-1; jj<=j+1; jj++)
                if (isValid(ii, jj) && !marked[ii][jj])
                    out &= dfs(ii, jj);
        return out;
  }
  // Is it a border of the board?
  private boolean isBorder(int i, int j) {
       return (i==0 || j==0 || i==M || j==N);
  }
  // Is it inside the board and “0”?
  private boolean isValid(int i, int j) { 
      return (i>=0 && j>=0 && i<M && j<N && !board[i][j]);
  }
}

I solved the problem by using a queue, I tried for so many cases and it works even if there are multiple islands; in case game is NOT over, it reports which node is not covered; I'll add output and the code as well

bool game_over = true;

1- create a matrix with the same size to keep track which nodes are visited, every node is NOT visited at the beginning,

2- if ( game_over) => Find an unvisited zero, if not found you are done, else go to step 6
3- Mark it as visited and push it to the queue
4- While queue is not empty and game_over
4-1: node = pop the front from q
4-2: for every neighbor of node
4-2-1: if neighbor is out of matrix => game_over = false
4-2-2: if neighbor = 1 => do nothing
4-2-3: if neighbor = 0 and neighbor is not visited => mark neighbor as visited and add neighbor to queue
5- Go back to step 2
6- Print game_over

#include <iostream>
using namespace std;

/*
Question:
Design an algo to decide if the GO game is over. i.e.
Given a boolean matrix, write a code to find if an island of 0's is completely surrounded by 1's.

Algo:
assume nxn matrix (i.e. 2D array)
seems like a graph problem

if assume only one island of 0's exits, that's simple: so check 0 is not located in the first and last row and column, if so, true and game over; otherwise, continue game

if multiple islands of 0's exit (some surrounded by 1's, some not), that's hard to let computer to judge.


Algo:
check each element in the matrix, once an unvisited 0 is found, a satisfying island is found only when all following are true:
1. The current element (Bij) with value 0 is not located in the first/last row/column
2. If any of the current element's 4 adjacent elements (Bi j-1, Bi, j+1, Bi-1 j, Bi+1 j) is unvisited and has value 0, mark it as visited and further check it satisfies condition 1; recursively check all adjacents' adjacent elements satisfy condition 1

Once a satisfying island is found, stop and game over; otherwise, continue check next element in the matrix

*/

bool oneFound(int row, int col, int** matrix, int** unvisited, int size) {

//check the current element
if (row==0)
{
//mark its lower adjacent element as visited, no need to check as must be unqualified as well
unvisited[row+1][col] = 1;
return false;
}
if (row==(size-1)) return false;
if (col==0)
{
//mark its right adjacent element as visited, no need to check as must be unqualified as well
unvisited[row][col+1] = 1;
return false;
}
if (col==(size-1)) return false;

//further check its 4 adjacent elements
bool flag_left=true;
bool flag_right =true;
bool flag_upper = true;
bool flag_lower = true;

if ((matrix[row][col-1]==0) && (unvisited[row][col-1]==0))
{
unvisited[row][col-1] =1;
flag_left = oneFound(row, col-1, matrix, unvisited, size);
}

if ((matrix[row][col+1]==0) && (unvisited[row][col+1]==0))
{
unvisited[row][col+1] =1;
flag_right = oneFound(row, col+1, matrix, unvisited, size);
}

if ((matrix[row-1][col]==0)&& (unvisited[row-1][col]==0))
{
unvisited[row-1][col] =1;
flag_upper = oneFound(row-1, col, matrix, unvisited, size);
}
if ((matrix[row+1][col]==0) && (unvisited[row+1][col]==0))
{
unvisited[row+1][col] =1;
flag_lower = oneFound(row+1, col, matrix, unvisited, size);
}

return (flag_left&&flag_right&&flag_upper&&flag_lower);
}


void islandFound(int** matrix, int** unvisited, int size) {
bool found=false;

for (int i=0; i<size; i++)
{
for (int j=0; j<size; j++)
{
if ((matrix[i][j]==0) &&(unvisited[i][j]==0)) //only need to check those unvisited 0 elements
{
unvisited[i][j] = 1; // mark current element as visited
if (oneFound(i,j, matrix, unvisited, size))
{
found = true; //set found flag to true
cout << "One 0's island surrounded by 1's was found. Game Over! \n";
break; //break the inner loop
}
}
}
if (found) break; //break the outer loop
}
if (!found) cout << "no such island can be found in the given matrix.\n";
}

int main() {

int** matrix = new int*[6];
for (int i=0; i<6; i++)
{
matrix[i] = new int[6];
for (int j=0; j<6; j++)
matrix[i][j] = 1; // initialise all elements as unvisited, 0: unvisited; 1: visited
}

matrix[0][3] =0;
matrix[1][3] =0;
matrix[3][2] =0;
matrix[3][3] =0;
matrix[4][2] =0;
matrix[5][2] =0;

int** unvisited = new int*[6];
for (int i=0; i<6; i++)
{
unvisited[i] = new int[6];
for (int j=0; j<6; j++)
unvisited[i][j] = 0; // initialise all elements as unvisited, 0: unvisited; 1: visited
}


int size = 6;
islandFound(matrix, unvisited, size);

int flag;
cout << "input any key to exit\n";
cin >> flag;
return 0;
}

india