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.
For example, given the following image:
[ "0010", "0110", "0100" ]
and x = 0, y = 2,
Return 6.
因为题目里说输入里只有一个全是1的联通域。所以这个问题转化为求值为1的点的left most position, right most position, top most position, bottom most position。
可以用DFS，遍历找出所有值为1的点，更新以上四个position value。
Time complexity O(mn)
1 public class Solution { 2 private int right; 3 private int left; 4 private int top; 5 private int bottom; 6 private final int[][] directions = {{0,-1},{0,1},{1,0},{-1,0}}; 7 8 public int minArea(char[][] image, int x, int y) { 9 if (image == null || image.length < 1) { 10 return 0; 11 } 12 int m = image.length, n = image[0].length; 13 bottom = 0; 14 top = m - 1; 15 right = 0; 16 left = n - 1; 17 boolean[][] visited = new boolean[m][n]; 18 dfs(image, x, y, visited); 19 int area = 0; 20 if (top <= bottom && left <= right) { 21 area = (bottom - top + 1) * (right - left + 1); 22 } 23 return area; 24 } 25 26 private void dfs(char[][] image, int x, int y, boolean[][] visited) { 27 if (x < 0 || x >= image.length || y < 0 || y >= image[0].length) { 28 return; 29 } 30 if (visited[x][y]) { 31 return; 32 } 33 if (image[x][y] != ‘1‘) { 34 return; 35 } 36 visited[x][y] = true; 37 // update left, right, top, bottom 38 if (x > bottom) { 39 bottom = x; 40 } 41 if (x < top) { 42 top = x; 43 } 44 if (y > right) { 45 right = y; 46 } 47 if (y < left) { 48 left = y; 49 } 50 // dfs 51 for (int i = 0; i < 4; i++) { 52 dfs(image, x + directions[i][0], y + directions[i][1], visited); 53 } 54 } 55 56 }
Discuss里给出了二分查找的方法。
Smallest Rectangle Enclosing Black Pixels 解答
原文：http://www.cnblogs.com/ireneyanglan/p/4946737.html