Capture Surrounded Regions Editorial

Practice Problem Link: Capture Surrounded Regions

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

You are given a matrix board of size n*m, containing either 'X' or 'O' in each cell. 'X' represents cells you own, and 'O' represents those you don't. You can capture regions that are surrounded by 'X' in all directions by turning each of their cells from 'O' to 'X'. Note: Two cells are connected if they share a common edge. You have to return the board configuration after you have captured as many cells as you can.

Approach

The Approach to solve this problem is to use DFS on a grid to fill the valid connected components with the given value. But, here we have to use DFS intelligently. Observe that only those connected components which have a cell at any of the boundaries of the matrix are invalid because they cannot be surrounded completely. So rather than marking those cells which are valid, we can mark those cells which are invalid, by applying DFS on those cells with ‘O’ and which are on the boundary of the matrix and lie in the same connected component. After that, we can just iterate on the matrix and and change those cells which are unvisited with ‘X’. 

Analysis

• Time Complexity: O(n * m)
• Space Complexity: O(n * m) // due to visited array

Implementation

C++

void dfs(vector<vector<char>> &board, vector<vector<bool>> &visited, int i, int j) {
	if(i < 0 || j < 0 || i >= board.size() || j >= board[0].size()) {
		return;
	}
	if(board[i][j] == 'X' || visited[i][j]) {
		return;
	}
	visited[i][j] = true;
	dfs(board, vis, i + 1, j);
	dfs(board, vis, i - 1, j);
	dfs(board, vis, i, j + 1);
	dfs(board, vis, i, j - 1);
}
vector<vector<char>> getFinalBoard(vector<vector<char>> board) {
    int n = board.size();
	int m = board[0].size();
	vector<vector<bool>> visited(n, vector<bool> (m, false));
	for (int i = 0; i < n; i++) {
		if(!visited[i][0] && board[i][0] == 'O') {
			dfs(board, visited, i, 0);
		}
		if(!visited[i][m - 1] && board[i][m - 1] == 'O') {
			dfs(board, visited, i, m - 1);
		}
	}
	for (int i = 0; i < m; i++) {
		if(!visited[0][i] && board[0][i] == 'O') {
			dfs(board, visited, 0, i);
		}
		if(!visited[n - 1][i] && board[n - 1][i] == 'O') {
			dfs(board, visited, n - 1, i);
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if(!visited[i][j] && board[i][j] == 'O') {
				board[i][j] = 'X';
			}
		}
	}
	return board;
}

Java

class Solution {
	void dfs(char[][] board, boolean[][] visited, int i, int j) {
		if(i < 0 || j < 0 || i >= board.length || j >= board[0].length) {
			return;
		}
		if(board[i][j] == 'X' || visited[i][j]) {
			return;
		}
		visited[i][j] = true;
		dfs(board, vis, i + 1, j);
		dfs(board, vis, i - 1, j);
		dfs(board, vis, i, j + 1);
		dfs(board, vis, i, j - 1);
	}
	char[][] getFinalBoard(char[][] board) {
    	int n = board.length;
		int m = board[0].length;
		boolean[][] visited = new boolean[n + 1][m + 1];
		for (int i = 0; i < n; i++) {
			if(!visited[i][0] && board[i][0] == 'O') {
				dfs(board, visited, i, 0);
			}
			if(!visited[i][m - 1] && board[i][m - 1] == 'O') {
				dfs(board, visited, i, m - 1);
			}
		}
		for (int i = 0; i < m; i++) {
			if(!visited[0][i] && board[0][i] == 'O') {
				dfs(board, visited, 0, i);
			}
			if(!visited[n - 1][i] && board[n - 1][i] == 'O') {
				dfs(board, visited, n - 1, i);
			}
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if(!visited[i][j] && board[i][j] == 'O') {
					board[i][j] = 'X';
				}
			}
		}
		return board;
	}
}