My Java solution


  • 0
    Q

    Originally I tried recursive solution and got stack overflow, so had to go with a queue.

    public class Solution {
            public void solve(char[][] board) {
                if (board.length == 0){
                    return;
                }
        		boolean[][] visited = new boolean[board.length][board[0].length];
        		for (int i=1;i<board.length-1;i++){
        			for (int j=1;j<board[0].length-1;j++){
        				if (board[i][j] == 'O'  && !visited[i][j]){
        					clearSurrounded(i, j, board, visited);
        				}
        			}
        		}
            }
        	private void clearSurrounded(int i,int j,char[][] board, boolean[][] globalVisited){
        		Set<Point> visited = new HashSet<Point>();
        		Deque<Point> q = new LinkedList<Point>();
        		q.add(new Point(i,j));
        		boolean surrounded = true;
        		while(!q.isEmpty()){
        			Point p = q.poll();
        			if (p.x<0 || p.y<0 || p.x>=board.length || p.y>=board[0].length){
        				surrounded = false;
        				continue;
        			}
        			if (visited.contains(p) || board[p.x][p.y] == 'X'){
        				continue;
        			}
        			visited.add(p);
        			globalVisited[p.x][p.y] = true;
        			
        			q.offer(new Point(p.x-1, p.y));
        			q.offer(new Point(p.x+1, p.y));
        			q.offer(new Point(p.x, p.y-1));
        			q.offer(new Point(p.x, p.y+1));
        		}
        		if (surrounded){
        			Iterator<Point> iter = visited.iterator();
        			while (iter.hasNext()){
        				Point p = iter.next();
        				board[p.x][p.y]='X';
        			}
        		}
        	}
        	
        	private class Point{
        		public Point (int x, int y){
        			this.x=x; 
        			this.y=y;
        		}
        		int x, y;
        		public boolean equals(Object obj){
        			Point other = (Point)obj;
        			if (x == other.x && y == other.y){
        				return true;
        			}
        			return false;
        		}
        		public int hashCode(){
        			return (x*1000)+y;
        		}
        	}
        }

Log in to reply
 

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