Is there any better solution?


  • 1
    Z

    This my solution about the problem and I do it in-place. I use DFS to travel the graph. I change the content to contain the parent infomation. I cost about 556 ms. Is there any better solution?

    class Solution:
    def print_maxtrix(self, board):
        x_length = len(board)
        y_length = len(board[0])
    
        x = 0
        while x < x_length:
            y = 0
            s = ''
            while y < y_length:
                s += board[x][y] + ' '
                y += 1
            print s
            x += 1
    
    def do_paint(self, board, x, y, curr_x, curr_y):
        while not(curr_x == x and curr_y == y):
            if (curr_x > 0) and (board[curr_x-1][curr_y] == 'O'):
                board[curr_x-1][curr_y] = 'C'
                curr_x -= 1
                continue
            
            if (curr_x < len(board) - 1) and (board[curr_x + 1][curr_y] == 'O'):
                board[curr_x+1][curr_y] = 'A'
                curr_x += 1
                continue
            
            if (curr_y > 0) and (board[curr_x][curr_y-1] == 'O'):
                board[curr_x][curr_y-1] = 'D'
                curr_y -= 1
                continue
    
            if (curr_y < len(board[0]) - 1) and (board[curr_x][curr_y + 1] == 'O'):
                board[curr_x][curr_y+1] = 'B'
                curr_y += 1
                continue
    
            if board[curr_x][curr_y] == 'A':
                curr_x -= 1
            elif board[curr_x][curr_y] == 'B':
                curr_y -= 1
            elif board[curr_x][curr_y] == 'C':
                curr_x += 1
            elif board[curr_x][curr_y] == 'D':
                curr_y += 1
    
    def paint_graph(self, board, x, y):
        board[x][y] = 'E'
        if (x > 0) and (board[x-1][y] == 'O'):
            board[x-1][y] = 'C'
            self.do_paint(board, x, y, x-1, y)
    
        if (x < len(board) -1) and (board[x+1][y] == 'O'):
            board[x+1][y] = 'A'
            self.do_paint(board, x, y, x+1, y)
    
        if (y > 0) and (board[x][y-1] == 'O'):
            board[x][y-1] = 'D'
            self.do_paint(board, x, y, x, y-1)
    
        if (y < len(board[0]) - 1) and (board[x][y+1] == 'O'):
            board[x][y+1] = 'B'
            self.do_paint(board, x, y, x, y+1)
    
    # @param board, a 2D array
    # Capture all regions by modifying the input board in-place.
    # Do not return any value.
    def solve(self, board):
        x_length = len(board)
        if x_length == 0: return
        
        y_length = len(board[0])
        if y_length == 0:  return
    
        # travel the outside cycle
        # top line
        curr = 0
        while curr < y_length:
            if board[0][curr] == 'O':
                self.paint_graph(board, 0, curr)
            curr += 1
        # right line
        curr = 0
        while curr < x_length:
            if board[curr][y_length-1] == 'O':
                self.paint_graph(board, curr, y_length-1)
            curr += 1
        #bottom line
        curr = y_length - 1
        while curr >= 0:
            if board[x_length-1][curr] == 'O':
                self.paint_graph(board, x_length-1, curr)
            curr -= 1
        # left line
        curr = x_length - 1
        while curr >= 0:
            if board[curr][0] == 'O':
                self.paint_graph(board, curr, 0)
            curr -= 1
        
        #print 'after paint'
        #self.print_maxtrix(board)
    
        # change the graph
        x = 0
        while x < x_length:
            y = 0
            while y < y_length:
                if board[x][y] == 'O':
                    board[x][y] = 'X'
                elif board[x][y] != 'X':
                    board[x][y] = 'O'
    
                y += 1
            x += 1

  • 3
    G

    I use BFS In Java, 560 ms.

    public class Solution {
    public static void solve(char[][] board) {
    		Queue<Integer> queue = new LinkedList<Integer>();
    		if (board == null || board.length == 0)
    			return;
    		int m = board.length;
    		int n = board[0].length;
    		boolean visited[][] = new boolean[m][n];
    		int dir[][] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
    		for (int i = 0; i < m; i++) {
    			for (int j = 0; j < n; j++) {
    				
    				//bfs
    				if (board[i][j] == 'O' && !visited[i][j]) {
    					boolean surounned = true;
    					List<Integer> visitedPoints = new ArrayList<Integer>();
    					queue.add(i * n + j);
    					visited[i][j] = true;
    					while (queue.size() > 0) {
    						int point = queue.poll();
    						visitedPoints.add(point);
    						int x = point/n;
    						int y = point%n;
    						for (int k = 0; k < 4; k++) {
    							int nextx = x + dir[k][0];
    							int nexty = y + dir[k][1];
    							if (nextx >= 0 && nextx < m && nexty >= 0 && nexty < n) {
    								if (board[nextx][nexty] == 'O' && !visited[nextx][nexty])
    									queue.add(nextx * n + nexty);
    								visited[nextx][nexty] = true;
    							} else {
    								surounned = false;
    							}
    						}
    					}
    					
    					if (surounned) {
    						for (int p : visitedPoints)
    							board[p / n][p % n] = 'X';
    					}
    				}
    			}
    		}
    	}
    

    }


Log in to reply
 

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