My DFS java solution (no stack overflow)


  • -1
    D
    public class Solution {
       Queue<int[]> q=new LinkedList<int[]>();
     public void solve(char[][] board) {
    	  if(board.length==0){
              return;
          }
            boolean[][] res=new boolean[board.length][board[0].length];
           
           
            int[][] visit=new int[board.length][board[0].length];
            for(int i=0;i<board.length;i++){
                for(int j=0;j<board[0].length;j++){
                    if((i==0 || i==board.length-1 ||j==0 ||j==board[0].length-1)&&board[i][j]=='O'){
                    	int[] tmp={i,j};
                    	q.offer(tmp);
                        helper(res,board,i,j,visit);
                        
                    }
                    
                    
                }
            }
           for(int i=0;i<board.length;i++){
                for(int j=0;j<board[0].length;j++){
                    if(board[i][j]=='O' && !res[i][j]){
                        board[i][j]='X';
                        
                    }
                    
                    
                }
            }
            
        }
        // use queue can prevent it from stackover flow cause function call needs build stack in memory
        private void helper(boolean[][] res,char[][] board,int i,int j,int[][] visit){
            while(!q.isEmpty()){
            	int[] input=q.poll();
            	i=input[0];
            	j=input[1];
        	if(i<board.length&&j<board[0].length&&i>=0&&j>=0&&visit[i][j]!=1 ){
                visit[i][j]=1;
                res[i][j]=true;
                
                if(board[i][j]=='O'){
                   
                    
                    	int[] tmp1={i-1,j};
                    	int[] tmp2={i,j-1};
                    	int[] tmp3={i+1,j};
                    	int[] tmp4={i,j+1};
                    	q.offer(tmp1);	              
                    	q.offer(tmp2);	                
                    	q.offer(tmp3);	                
                    	q.offer(tmp4);
                  
                    
                }
                
                
                
            }
           
            
            }
            return;
        }
    

    }


Log in to reply
 

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