Question

Formatted question description: https://leetcode.ca/all/130.html

130	Surrounded Regions

Given a 2D board containing 'X' and '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

Algorithm

It’s a bit like “Go” chess, turning all the enclosed O into X, but the difference is that the O on the edge is not counted as being captured.

It is similar to the previous number of Islands and can be solved by DFS. At the beginning, my idea was that DFS traverses the O in the middle. If it does not reach the edge, it becomes X. If it reaches the edge, it changes back to the X before it.

However, it is very expensive to do this. The common practice seen on the Internet is to scan the four sides of the matrix. If there is an O, use DFS to traverse and change all consecutive Os into another character, such as $, so that the remaining The next Os are all captured, then change these Os into X, and change the $ back to O.

Code

Java

  • import java.util.HashSet;
    import java.util.LinkedList;
    import java.util.Queue;
    
    public class Surrounded_Regions {
    
    	 public class Solution_bfs {
    
    	     // record visited positions
    	     HashSet<String> hs = new HashSet<String> ();
    
    	     // BFS, using queue
    	     public void solve(char[][] board) {
    	         if (board == null || board.length == 0)     return;
    
    	         int row = board.length;
    	         int column = board[0].length;
    
    	         // search each edge
    	         for (int i = 0; i < row; i++) {
    	             for (int j = 0; j < column; j++) {
    
    	                 // find edge
    	                 if (i == 0 || i == row - 1 || j  == 0 || j == column - 1) {
    
    	                     if (board[i][j] == 'O') {
    
    	                         // key is compressed as "i_j"
    	                         if (!hs.contains(getKey(i, j))) {
    
    	                             // @note: like doing add when enqueue, also dont add it here, add ONLY happens after dequeue
    	                             // hs.add(i+"_"+j);
    	                             BFS(board, i, j);
    	                         }
    	                     }
    	                 }
    	             }
    	         }
    
    	         // if a position is not in hashset, then its "X"
    	         for (int i = 0; i < row; i++) {
    	             for (int j = 0; j < column; j++) {
    
    	                 if (!hs.contains(getKey(i, j)))
    	                     board[i][j] = 'X';
    	             }
    	         }
    
    	     }
    
    	     public void BFS (char[][] board, int inow, int jnow) {
    
    	         Queue<String> q = new LinkedList<String>();
    	         q.offer(getKey(inow, jnow));
    
    	         while (!q.isEmpty()) {
    	             String keycode = q.poll();
    	             String[] array = keycode.split("_");
    	             int i = Integer.parseInt(array[0]), j = Integer.parseInt(array[1]);
    
    	             if (board[i][j] == 'O' && !hs.contains(getKey(i, j))) {
    	                 hs.add(getKey(i, j));
    
    	                 // search neighbours of this position, find "O" and enqueue
    	                 //@note: dont consider positions on edge, since they are safe. just enqueue those NOT-edge
    	                 //      I was messed up by checking elements on edge, but no need
    	                 if (isValid(i + 1, j, board) && board[i + 1][j] == 'O' && !hs.contains(getKey(i + 1, j)))
    	                     {
    	                         q.offer(getKey(i + 1, j));
    
    	                         /*
    	                             @note: dont add to hashset here, if add here, next dequeue and get this one,
    	                                     it's not going to search its neighbours since it is in hashset
    	                         */
    	                         // hs.add(getKey(i + 1, j));
    	                     }
    
    	                 if (isValid(i - 1, j, board) && board[i - 1][j] == 'O' && !hs.contains(getKey(i - 1, j)))
    	                     {   q.offer(getKey(i - 1, j));  /* hs.add(getKey(i - 1, j));*/ }
    
    	                 if (isValid(i, j + 1, board) && board[i][j + 1] == 'O' && !hs.contains(getKey(i, j + 1)))
    	                     {   q.offer(getKey(i, j + 1));  /* hs.add(getKey(i, j + 1));*/ }
    
    	                 if (isValid(i, j - 1, board) && board[i][j - 1] == 'O' && !hs.contains(getKey(i, j - 1)))
    	                     {   q.offer(getKey(i, j - 1));  /* hs.add(getKey(i, j + 1));*/ }
    	             }
    
    	         }
    	     }
    
    	     public boolean isValid(int i, int j, char[][] board) {
    	         int row = board.length;
    	         int column = board[0].length;
    
    	         if (i >= row || i < 0 || j >= column || j < 0)
    	             return false;
    	         else
    	             return true;
    	     }
    
    	     public String getKey(int i, int j) {
    
    	         return i+"_"+j;
    	     }
    	 }
    
    
    	// re-write dfs, check validity before next recursion. no bird use
    	public class Solution_dfs_improved {
    	    public void solve(char[][] board) {
    
    	        if (board.length == 0 || board[0].length == 0) {
    	            return;
    	        }
    	        // if 'O' is somehow connected to boarder, then it's alive. NOT the same as GO chess
    
    	        // if a single 'O' is alive, mark it as '.', then change it back to 'O' after flipping those trapped ones
    
    	        int rowNum = board.length;
    	        int colNum = board[0].length;
    
    	        for (int i = 0; i < rowNum; i++) {
    	            for (int j = 0; j < colNum; j++) {
    
    	                // try dfs on all 'O's on 4 boarders
    	                if ((i == 0 || i == rowNum - 1 || j == 0 || j == colNum - 1)
    	                    && board[i][j] == 'O') { // @note: accelaration is, if previous dfs modified some 'O', then no repeat dfs
    	                    // System.out.println("before one dfs: " + Arrays.deepToString(board));
    	                    dfs(board, i, j);
    	                }
    	            }
    	        }
    
    	        // flip trapped 'O's
    	        for (int i = 0; i < rowNum; i++) {
    	            for (int j = 0; j < colNum; j++) {
    
    	                if (board[i][j] == 'O') {
    	                    board[i][j] = 'X';
    	                }
    	            }
    	        }
    
    	        // restore alive 'O's
    	        for (int i = 0; i < rowNum; i++) {
    	            for (int j = 0; j < colNum; j++) {
    
    	                if (board[i][j] == '.') {
    	                    board[i][j] = 'O';
    	                }
    	            }
    	        }
    
    	    }
    
            public void dfs(char[][] b, int i, int j) {
    
                if (b[i][j] == 'O') {
                    b[i][j] = '.';
                }
    
                // isValid() will also check if visited
                if (isValid(b, i + 1, j) && b[i + 1][j] == 'O')     dfs(b, i + 1, j);
                if (isValid(b, i - 1, j) && b[i - 1][j] == 'O')     dfs(b, i - 1, j);
                if (isValid(b, i, j + 1) && b[i][j + 1] == 'O')     dfs(b, i, j + 1);
                if (isValid(b, i, j - 1) && b[i][j - 1] == 'O')     dfs(b, i, j - 1);
            }
    
            public boolean isValid(char[][] b, int i, int j) {
                int row = b.length, col = b[0].length;
    
                if (i >= row || i < 0 || j >= col || j < 0)
                    return false;
                else
                    return true;
            }
    	}
    
    
    	// stackoverflow at dfs
    	public class Solution_dfs_over_limit {
    	    public void solve(char[][] board) {
    
    	        if (board.length == 0 || board[0].length == 0) {
    	            return;
    	        }
    	        // if 'O' is somehow connected to boarder, then it's alive. NOT the same as GO chess
    
    	        // if a single 'O' is alive, mark it as '.', then change it back to 'O' after flipping those trapped ones
    
    	        int rowNum = board.length;
    	        int colNum = board[0].length;
    
    	        for (int i = 0; i < rowNum; i++) {
    	            for (int j = 0; j < colNum; j++) {
    
    	                // try dfs on all 'O's on 4 boarders
    	                if ((i == 0 || i == rowNum - 1 || j == 0 || j == colNum - 1)
    	                    && board[i][j] == 'O') { // @note: accelaration is, if previous dfs modified some 'O', then no repeat dfs
    	                    dfs(board, i, j);
    	                }
    	            }
    	        }
    
    	        // flip trapped 'O's
    	        for (int i = 0; i < rowNum; i++) {
    	            for (int j = 0; j < colNum; j++) {
    
    	                if (board[i][j] == 'O') {
    	                    board[i][j] = 'X';
    	                }
    	            }
    	        }
    
    	        // restore alive 'O's
    	        for (int i = 0; i < rowNum; i++) {
    	            for (int j = 0; j < colNum; j++) {
    
    	                if (board[i][j] == '.') {
    	                    board[i][j] = 'O';
    	                }
    	            }
    	        }
    
    	    }
    
    	    private void dfs(char[][] board, int i, int j) {
    
    	        if (i < 0 || j < 0 || i >= board.length || j >= board[0].length) {
    	            return;
    	        }
    
    	        // if it's 'X', dont't do dfs
    	        if (board[i][j] != 'O') { // @note: i missed thsi check, and fill full board with '.' ...
    	            return;
    	        }
    
    	        board[i][j] = '.';
    
    	        dfs(board, i - 1, j);
    	        dfs(board, i + 1, j);
    	        dfs(board, i, j - 1);
    	        dfs(board, i, j + 1);
    	    }
    	}
    }
    
  • // OJ: https://leetcode.com/problems/surrounded-regions/
    // Time: O(MN)
    // Space: O(MN)
    class Solution {
    public:
        void solve(vector<vector<char>>& A) {
            int M = A.size(), N = A[0].size(), dirs[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
            function<void(int, int)> dfs = [&](int x, int y) {
                if (x < 0 || x >= M || y < 0 || y >= N || A[x][y] != 'O') return;
                A[x][y] = '#';
                for (auto &[dx, dy] : dirs) dfs(x + dx, y + dy);
            };
            for (int i = 0; i < M; ++i) dfs(i, 0), dfs(i, N - 1);
            for (int j = 0; j < N; ++j) dfs(0, j), dfs(M - 1, j);
            for (int i = 0; i < M; ++i) {
                for (int j = 0; j < N; ++j) {
                    A[i][j] = A[i][j] == '#' ? 'O' : 'X';
                }
            }
        }
    };
    
  • class UnionFind():
      def __init__(self, m, n):
        self.dad = [i for i in range(0, m * n)]
        self.rank = [0 for i in range(0, m * n)]
        self.m = m
        self.n = n
    
      def find(self, x):
        dad = self.dad
        if dad[x] != x:
          dad[x] = self.find(dad[x])
        return dad[x]
    
      def union(self, xy):
        dad = self.dad
        rank = self.rank
        x, y = map(self.find, xy)
        if x == y:
          return False
        if rank[x] > rank[y]:
          dad[y] = x
        else:
          dad[x] = y
          if rank[x] == rank[y]:
            rank[y] += 1
        return True
    
    
    class Solution:
      # @param {list[list[str]]} board a 2D board containing 'X' and 'O'
      # @return nothing 
      def solve(self, board):
        # Write your code here
        if len(board) == 0:
          return
        regions = set([])
        n, m = len(board), len(board[0])
        uf = UnionFind(len(board[0]), len(board))
        directions = {"u": (-1, 0), "d": (1, 0), "l": (0, -1), "r": (0, 1)}
        for i in range(0, len(board)):
          for j in range(0, len(board[0])):
            if board[i][j] == 'X':
              continue
            for d in ["d", "r"]:
              di, dj = directions[d]
              newi, newj = i + di, j + dj
              if newi >= 0 and newi < len(board) and newj >= 0 and newj < len(board[0]):
                if board[newi][newj] == "O":
                  uf.union((newi * m + newj, i * m + j))
    
        for i in range(0, len(board)):
          for j in [0, len(board[0]) - 1]:
            if board[i][j] == "O":
              regions.add(uf.find(i * m + j))
    
        for j in range(0, len(board[0])):
          for i in [0, len(board) - 1]:
            if board[i][j] == "O":
              regions.add(uf.find(i * m + j))
    
        for i in range(0, len(board)):
          for j in range(0, len(board[0])):
            if board[i][j] == "O" and uf.find(i * m + j) not in regions:
              board[i][j] = "X"
    
    

All Problems

All Solutions