[LeetCode 302] Smallest Rectangle Enclosing Black Pixels (Hard**)

An image is represented by a binary matrix with 0 as a white pixel and 1 as a black pixel. The black pixels are connected, i.e., there is only one black region. Pixels are connected horizontally and vertically. Given the location (x, y) of one of the black pixels, return the area of the smallest (axis-aligned) rectangle that encloses all black pixels.

Example:

Input:
[
  "0010",
  "0110",
  "0100"
]
and x = 0, y = 2

Output: 6

Solution: BFS

1. 从给定的起点开始用BFS，访问每个1点，对每个点不断更新 left most col, right most col, top most row and bottom most row
2. 最后最小面积就是 宽 * 高

class Solution {
    public int minArea(char[][] image, int x, int y) {
        if (image == null || image.length == 0 || image[0].length == 0) {
            return 0;
        }
        
        Queue<int[]> queue1 = new LinkedList<> ();
        Queue<int[]> queue2 = new LinkedList<> ();
        queue1.offer (new int[] {x, y});
        
        boolean[][] visited = new boolean[image.length][image[0].length];
        visited[x][y] = true;
        
        int left = Integer.MAX_VALUE;
        int right = Integer.MIN_VALUE;
        int top = Integer.MAX_VALUE;
        int bottom = Integer.MIN_VALUE;
        
        while (!queue1.isEmpty ()) {
            int[] node = queue1.poll ();
            int row = node[0];
            int col = node[1];
            
            left = Math.min (left, col);
            right = Math.max (right, col);
            top = Math.min (top, row);
            bottom = Math.max (bottom, row);
            
            int[][] directions = {{-1, 0},{0, 1},{1, 0},{0, -1}};
            
            for (int[] direction : directions) {
                int nextRow = row + direction[0];
                int nextCol = col + direction[1];
                
                if (nextRow >= 0 && nextRow < image.length && nextCol >= 0 && nextCol < image[0].length && !visited[nextRow][nextCol]) {
                    visited[nextRow][nextCol] = true;
                    //System.out.println (nextRow + " : " + nextCol);
                    if (image[nextRow][nextCol] == '1') {
                        //System.out.println (nextRow + " : " + nextCol);
                        queue2.offer (new int[] {nextRow, nextCol});
                    }
                }
            }
            
            if (queue1.isEmpty ()) {
                queue1 = queue2;
                queue2 = new LinkedList<> ();
            }
        }
        
        
        return (right - left + 1) * (bottom - top + 1);
    }
}