DFS from edges to mark which 'O's gonna live, then iterate through the list list to capture/save


  • 0

    Our goal is to simulate what happens if we continuously keep capturing 'O' until there is nothing more to capture. The end result is, only those cells that connects to a edge with 'O's chain, they are save, every other 'O' gets captures. This means, if we do DFS from each 'O' on edge, by marking the 'O' and neighboring 'O's then, we know which 'O' are ultimately going to be safe. We mark them with '#'.

    Finally, we run over the entire matrix once, update all 'O' (these are the those unlucky ones which didn't get marked as '#') to 'X' and update all '#' to 'O'.

    public class Solution {
    	public void solve(char[][] board) {
    		int height = board.length;
    		if (height < 1) {
    			return;
    		}
    		int width = board[0].length;
    		
    		for (int i = 0; i < height; i++) {
    			if (board[i][0] == 'O') {
    				dfs(board, i,0, height, width);
    			}
    			if (width>1 && board[i][width - 1] == 'O') {
    				dfs(board,i,width - 1, height, width);
    			}
    		}
    		
    		for (int i = 0; i < width; i++) {
    			if (board[0][i] == 'O') {
    				dfs(board,0,i, height, width);
    			}
    			if (board[height - 1][i] == 'O') {
    				dfs(board,height - 1,i, height, width);
    			}
    		}
    		
    		for (int i = 0; i < board.length; i++) {
    			for (int j = 0; j < board[0].length; j++) {
    				switch (board[i][j]) {
    					case 'O':board[i][j] = 'X'; break;
    					case '#':board[i][j] = 'O'; break;
    				}
    				
    			}
    		}
    	}
    	
    	void dfs(char[][] vec,int i,int j,int height,int width){
    		if(vec[i][j]=='O'){
    			vec[i][j]='#';
    			if(i>1)
    				dfs(vec,i-1,j,height,width);
    			if(j>1)
    				dfs(vec,i,j-1,height,width);
    			if(i+1<height)
    				dfs(vec,i+1,j,height,width);
    			if(j+1<width)
    				dfs(vec,i,j+1,height,width);
    		}
    	}
    }
    

Log in to reply
 

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