130. Surrounded Regions

Surrounded Regions

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

For example,

X X X X X O O X X X O X X O X X

After running your function, the board should be:

X X X X X X X X X X X X X O X X

Solution

public class Solution {
        public void solve(char[][] board) {


        int m = board.length;
        if (m == 0)
            return;
        int n = board[0].length;

        boolean[][] visited = new boolean[m][n];
        List<Integer> queue = new ArrayList<>();

        for (int i = 0; i < n - 1; i++) {
            queue.add(convert(0, i, m, n));
        }

        for (int i = 0; i < m - 1; i++) {
            queue.add(convert(i, n - 1, m, n));

        }

        for (int i = n - 1; i > 0; i--) {
            queue.add(convert(m - 1, i, m, n));

        }

        for (int i = m - 1; i > 0; i--) {
            queue.add(convert(i, 0, m, n));
        }

        if (m==1 && n ==1) {
            queue.add(convert(0,0,m,n));
        }

        while (!queue.isEmpty()) {
            int currentNum = queue.remove(0);
            int x = currentNum / n;
            int y = currentNum - x * n;

            visited[x][y] = true;
            if (board[x][y] == 'O') {
                board[x][y] = '1';

                if (validate(m, n, x + 1, y) && !visited[x + 1][y]) {
                    queue.add(convert(x + 1, y, m, n));
                }

                if (validate(m, n, x - 1, y) && !visited[x - 1][y]) {
                    queue.add(convert(x - 1, y, m, n));
                }

                if (validate(m, n, x, y - 1) && !visited[x][y - 1]) {
                    queue.add(convert(x, y - 1, m, n));
                }

                if (validate(m, n, x, y + 1) && !visited[x][y + 1]) {
                    queue.add(convert(x, y + 1, m, n));
                }
            }
        }


        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                } else if (board[i][j] == '1') {
                    board[i][j] = 'O';
                }
            }
        }

    }


    public int convert(int x, int y, int m, int n) {
        return n * x + y;
    }

    public boolean validate(int m, int n, int x, int y) {
        if (x >= 0 && x < m && y >= 0 && y < n) {
            return true;
        }

        return false;
    }
}