very easy to understand java solution


  • 0
    public class Solution {
        
    public class Pair {
    	public int _a;
    	public int _b;
    	Pair(int a, int b){
    		_a = a;
    		_b = b;
    	}
    }
    	    public void solve(char[][] board) {
    	    	//null is unavailable
    	    	//size less than 3, then no cell is surrounded
    	    	if(board == null || board.length < 3 || board[0].length < 3) return ;
    	    	int row = board.length, col = board[0].length;
    	    	//mark 4 edges
    	    	for(int r = 0; r < row; r++){
    	    		markEdge(board, r, 0);
    	    		markEdge(board, r, col-1);
    	    	}
    	    	for(int c = 0; c < col; c++){
    	    		markEdge(board, 0, c);
    	    		markEdge(board, row-1, c);
    	    	}
    	    	for(int r = 0; r < row; r++){
    	    		for(int c = 0; c < col; c++){
    	    			resetBoard(board,r,c);
    	    		}
    	    	}
    	    }
    
    		private void markEdge(char[][] board, int r, int c) {
    			if(board[r][c] == 'O'){
    				Queue<Pair> q = new LinkedList<>();
    				q.add(new Pair(r,c));
    				traceArea(board, q);
    			}
    		}
    
    		private void traceArea(char[][] board, Queue<Pair> q) {
    			// TODO Auto-generated method stub
    			while(!q.isEmpty()){
    				int row = q.peek()._a;
    				int col = q.peek()._b;
    				q.poll();
    				if(board[row][col] != 'A'){
        				board[row][col] = 'A';
        				checkPush(board, q, row-1, col);
        				checkPush(board, q, row+1, col);
        				checkPush(board, q, row, col+1);
        				checkPush(board, q, row, col-1);
    				}
    			}
    		}
    
    		private void checkPush(char[][] board, Queue<Pair> q, int r, int c) {
    			if(r < 0 || c < 0 || r >= board.length || c >= board[0].length) return;
    			if(board[r][c] == 'O') q.add(new Pair(r,c));
    		}
    
    		private void resetBoard(char[][] board, int r, int c) {
    			switch(board[r][c]){
    			case 'O':
    				board[r][c] = 'X';
    				break;
    			case 'A':
    				board[r][c] = 'O';
    				break;
    			}
    		}
    	}
    

Log in to reply
 

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