JAVA-----------Easy Version To UnderStand!!!!!!!!!!!!


  • 14
    H

    Use BFS.This problem is similar to Number of Islands. In this problem, only the cells on the boarders can not be surrounded. So we can first merge those O's on the boarders like in Number of Islands and replace O's with 'B', and then scan the board and replace all O's left (if any).

    class Point {
    int x;
    int y;
    Point(int x, int y) {
    	this.x = x;
    	this.y = y;
    }
    

    }

    public static void solve(char[][] board) {
    	if (board == null || board.length == 0)
    		return;
    	int rows = board.length, columns = board[0].length;
    	int[][] direction = { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } };
    	for (int i = 0; i < rows; i++)
    		for (int j = 0; j < columns; j++) {
    			if ((i == 0 || i == rows - 1 || j == 0 || j == columns - 1) && board[i][j] == 'O') {
    				Queue<Point> queue = new LinkedList<>();
    				board[i][j] = 'B';
    				queue.offer(new Point(i, j));
    				while (!queue.isEmpty()) {
    					Point point = queue.poll();
    					for (int k = 0; k < 4; k++) {
    						int x = direction[k][0] + point.x;
    						int y = direction[k][1] + point.y;
    						if (x >= 0 && x < rows && y >= 0 && y < columns && board[x][y] == 'O') {
    							board[x][y] = 'B';
    							queue.offer(new Point(x, y));
    						}
    					}
    				}
    			}
    		}
    	for (int i = 0; i < rows; i++)
    		for (int j = 0; j < columns; j++) {
    			if (board[i][j] == 'B')
    				board[i][j] = 'O';
    			else if (board[i][j] == 'O')
    				board[i][j] = 'X';
    		}
    
    }

  • 1

    Good thought ! You mark all the 0's which can not be surrounded with B's and then the left 0's on the board are those that can be replaced with X's. And then replace all the B's with 0's so the problem is solved.


  • 0

    @HelloWorld123456 i just don't know what's the meaning of direction[][], can you explain it? thank you...


  • 1
    J

    @yaqi13 direction[][] is for searching the four directions of one point. Say for board[i][j], we should check board[i-1][j], board[i+1][j], board[i][j-1], board[i][j+1], but with direction array, we could write this process in a for-loop. Hope this can help you.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.