Leetcode: Surrounded Regions
This question is asked at Google, Amazon, and Uber.
It is the following:
Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in the surrounding region.
Here's what we are trying to do:
We're attempting to first see which regions are surrounded, any 'O' that is not on the border and is not connected to an 'O' on the border will be flipped to 'X'. Here's an example:
You can see everything else is surrounded in all 4 directions, but not the 4th row, 2nd column. This is very similar to the capture rule in the game of go:
The only difference is that the cells are considered to be escaped from the surrounding if it reaches any border. It can either use a Depth-First-Search of Breadth-First-Search. The goal of the problem is to mark those captured cells. Here are the steps:
1. Select all the cells that are located on the borders of the board. We first select all cells that are located on the borders of the board and see which cells are not connected.
2. We have 3 cells, the X cell, the O cell, and the E cell.
The X cell represents the wall.
O cells that have no connection to the border are Covered, which should be covered with X.
E letter are marked during the DFS traversal, and these cells have at least one connection to the borders, which are not captured. These cells are known as O.
public class Solution {
//number of rows and number of columns
protected Integer ROWS = 0;
protected Integer COLS = 0;
public void solve(char[][] board) {
//set number of rows or columns
if(board == null || board.length == 0) {
return;
}
this.ROWS = board.length;
this.COLS = board[0].length;
List<Pair<Integer, Integer>> borders = new LinkedList<Pair<Integer, Integer>>();
//add all the edges
for(int r = 0; r < this.ROWS, ++r) {
borders.add(new Pair(r, 0));
borders.add(new Pair(r, this.COLS - 1));
}
for(int c = 0; c < this.COLS; ++c) {
borders.add(new Pair(0, c));
borders.add(new Pair(this.ROWS - 1, c));
}
for(Pair<Integer, Integer> pair : borders) {
this.DFS(board, pair.first, pair.second);
}
//Switch to proper form, See which is marked as 'e' and set that as the regions that aren't surrounded.
for(int r = 0; r < this.ROWS; ++r) {
for(int c = 0; c < this.COLS; ++c) {
if(board[r][c] == 'O'){
board[r][c] = 'X';
}
if(board[r][c] == 'E') {
board[r][c] = 'O';
}
}
}
protected void DFS(char[][] board, int row, int col) {
//skip if this region is a wall
if(board[row][col] != 'O') {
return;
}
//else set a region as a temporary mark
//traverse through all the directions
board[row][col] = 'E';
if(col < this.COLS - 1) {
this.DFS(board, row, col + 1);
}
if(row < this.ROWS - 1) {
this.DFS(board, row + 1, col);
}
if(col > 0) {
this.DFS(board, row, col - 1);
}
if(row > 0) {
this.DFS(board, row - 1, col);
}
}
}
}
class Pair<U, V> {
public U first;
public V second;
//Data structure denoting points in a graph.
public Pair(U first, V second) {
this.first = first;
this.second = second;
}
}
The BFS algorithm is very similar, with a few modifications. Everything is the same besides the method that calls BFS.
protected void BFS(char[][] board, int r, int c) {
//new linked list
LinkedList<Pair<Integer, Integer>> queue = new LinkedList<Pair<Integer, Integer>>();
queue.offer(new Pair<>(r,c));
//while queue is not empty append the neighbors until there are no more for each edge point,
while(!queue.isEmpty()) {
Pair<Integer, Integer> pair = queue.pollFirst();
int row = pair.first;
int col = pair.second;
if(board[row][col] != 'O')
continue;
//mark the index
board[row][col] = 'E';
if(col < this.COLS - 1) {
queue.offer(new Pair<>(row, col + 1));
}
if(row < this.ROWS - 1) {
queue.offer(new Pair<>(row + 1, col));
}
if(col > 0) {
queue.offer(new Pair<>(row, col - 1));
}
if(row > 0) {
queue.offer(new Pair<>(row + 1, col));
}
}
}
So basically if we are telling 2 points we can introduce a third variable to keep track, and perform a switcheroo at the end.
Comments
Post a Comment