Mark Enclosed Regions

Problem

Mark Enclosed Regions
Let A be a 2D array whose entries are either W or B, write a program that takes A, and replaces all Ws that can not reach the boundary with a B.
For example Given:
W B B W W
W W B W W
B W W B B
W B W W W
B W W W B
The final result should be:
W B B W W
W W B x W
B W x B B
W B x x W
B W W W B

Solution

This is a tedious problem, we need to handle many edge conditions. The key is to be organized.

Firstly, lets mark the key indexes:

       0 1     M-2 M-1

     0 W B W W B W 

     1 B B x B W W 

       B B x B W B

       B W x x B B

   N-2 W B B W x W

   N-1 W B W B W W

The row 0 and N - 1 don't have to be considered. The column 0 and M - 1 don't have to be considered.

The row 1 and N - 2 need to be considered. The column 1 and M - 2 need to be considered.

There are 4 points as special cases: [1, 1], [1, M - 2], [N - 2, 1], [N - 2, M - 2].

For points in square 2 <= row <= N - 3 and 2 <= column <= M - 3, all the W should be marked.

The rest of the tasks is to quickly write the program according to these scenarios without making mistakes.

public class EnclosedRegion {
  public static void fill(char[][] a) {
    int N = a.length;
    int M = a[0].length;
    if(N <= 2 || M <= 2) return;
 
    for(int j = 1; j < M - 1; j++) {
      if(a[1][j] == 'W' && a[0][j] == 'W') {
        if(j == 1 && a[1][0] == 'W') {
          a[1][1] = 'x';
        } else if(j == M - 2 && a[1][M - 1] == 'W') {
          a[1][j] = 'x';
        } else if(j != 1 && j != M - 2) {
          a[1][j] = 'x';
        }
      }
    }
 
    for(int j = 1; j < M - 1; j++) {
      if(a[N - 2][j] == 'W' && a[N - 1][j] == 'W') {
        if(j == 1 && a[N - 2][0] == 'W') {
          a[N - 2][1] = 'x';
        } else if(j == M - 2 && a[N - 2][M - 1] == 'W') {
          a[N - 2][M - 2] = 'x';
        } else if(j != 1 && j != M - 2) {
          a[N - 2][j] = 'x';
        }
      }
    }

    for(int i = 1; i < N - 1; i++) {
      if(a[i][1] == 'W' && a[i][0] == 'W') {
        if(i == 1 && a[0][1] == 'W') {
          a[1][1] = 'x';
        } else if(i == N - 2 && a[N - 1][1] == 'W') {
          a[N - 2][1] = 'x';
        } else if(i != 1 && i != N - 2) {
          a[i][1] = 'x';
        }
      }
    }
 
    for(int i = 1; i < N - 1; i++) {
      if(a[i][M - 2] == 'W' && a[i][M - 1] == 'W') {
        if(i == 1 && a[0][M - 2] == 'W') {
          a[1][M - 2] = 'x';
        } else if(i == N - 2 && a[N - 1][M - 2] == 'W') {
          a[N - 2][M - 2] = 'x';
        } else if(i != 1 && i != N - 2) {
          a[i][M - 2] = 'x';
        }
      }
    }
 
    for(int i = 2; i < N - 2; i ++) {
      for(int j = 2; j < M - 2; j ++) {
        if(a[i][j] == 'W')
          a[i][j] = 'x';
      }
    }
 
  }
  public static void main(String...args) {
    char[][] a = new char[][] {
      {'W', 'B', 'B', 'W', 'W'},
      {'W', 'W', 'B', 'W', 'W'},
      {'B', 'W', 'W', 'B', 'B'},
      {'W', 'B', 'W', 'W', 'W'},
      {'B', 'W', 'W', 'W', 'B'}
    };
    print(a);
    fill(a);
    System.out.println("=====================================");
    print(a);
  }
  private static void print(char[][] a) {
    int N = a.length;
    int M = a[0].length;
    for(int i = 0; i < N; i++) {
      for(int j = 0; j < M; j++) {
        System.out.print(a[i][j] + " ");
      }
      System.out.println();
    }
  }
}

We need to exam every element in the 2D array, the time cost is O(NM), we need space to store the 2D array, the time cost is O(NM)