Skip to content

Instantly share code, notes, and snippets.

@gogsbread
Last active December 20, 2015 18:59
Show Gist options
  • Save gogsbread/6179593 to your computer and use it in GitHub Desktop.
Save gogsbread/6179593 to your computer and use it in GitHub Desktop.
leetcode - surrounding regions
public class Solution {
private static int M;
private static int N;
public void solve(char[][] board) {
M = board.length;
N = board[0].length;
//graph = new Node[M, N];
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++)
if (board[i][j] == 'O')
MarkRegions(board, i, j);
}
static boolean CheckTop(char[][] board, int m, int n)
{
boolean isBounded = false;
//scan top
if (m - 1 >= 0)
{
if (board[m - 1][n] == 'O')
isBounded = CheckTop(board, m - 1, n);
else
isBounded = true;
}
return isBounded;
}
static boolean CheckBottom(char[][] board, int m, int n)
{
boolean isBounded = false;
if (m + 1 < M)
{
if (board[m + 1][n] == 'O')
isBounded = CheckBottom(board, m + 1, n);
else
isBounded = true;
}
return isBounded;
}
static boolean CheckLeft(char[][] board, int m, int n)
{
boolean isBounded = false;
if (n - 1 >= 0)
{
if (board[m][n - 1] == 'O')
isBounded = CheckLeft(board, m, n - 1);
else
isBounded = true;
}
return isBounded;
}
static boolean CheckRight(char[][] board, int m, int n)
{
boolean isBounded = false;
if (n + 1 < N)
{
if (board[m][n + 1] == 'O')
isBounded = CheckRight(board, m, n + 1);
else
isBounded = true;
}
return isBounded;
}
static void MarkRegions(char[][] board, int m, int n)
{
boolean result = CheckTop(board,m,n) && CheckBottom(board,m,n) && CheckLeft(board,m,n) && CheckRight(board,m,n);
if (result)
board[m][n] = 'X';
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment