描述
一个由二进制矩阵表示的图，0 表示白色像素点，1 表示黑色像素点。黑色像素点是联通的，即只有一块黑色区域。像素是水平和竖直连接的，给一个黑色像素点的坐标 (x, y) ，返回囊括所有黑色像素点的矩阵的最小面积。
样例
举个例子，给一个图
[
"0010",
"0110",
"0100"
]
并且给出x = 0, y = 2, 则返回 6。
思路
分为几个模块
四个方向的查找方法，以及在查找过程中使用的判断是否为0的方法(判断行是空的，
行固定列在变，判断列是空的列固定行在变），以及异常情况
查找函数相当于在计算，所以直接在调用函数时在形参里输入参数；
行和列极易混淆，每一步传入参数都要仔细检查
注意
列判断方法的构造：
列不变，行在变，通过对比得到布尔值
行判断方法的构造：
行不变，列在变，通过对比得到布尔值
代码
public class Solution {
public int minArea(char[][] image, int x, int y) {
if (image == null || image.length == 0 || image[0].length == 0) {
return 0;
}
int left = findLeft(image, 0, y);
int right = findRight(image, y, image[0].length - 1);
int top = findTop(image, 0, x);
int bottom = findBottom(image, x, image.length - 1);
return (right - left + 1) * (bottom - top + 1);
}
private int findLeft(char[][] image, int start, int end) {
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (isEmptyColumn(image, mid)) {
start = mid;
} else {
end = mid;
}
}
if (isEmptyColumn(image, start)) {
return end;
} else {
return start;
}
}
private int findRight(char[][] image, int start, int end) {
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (isEmptyColumn(image, mid)) {
end = mid;
} else {
start = mid;
}
}
if (isEmptyColumn(image, end)) {
return start;
} else {
return end;
}
}
private int findTop(char[][] image, int start, int end) {
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (isEmptyRow(image, mid)) {
start = mid;
} else {
end = mid;
}
}
if (isEmptyRow(image, start)) {
return end;
} else {
return start;
}
}
private int findBottom(char[][] image, int start, int end) {
while (start + 1 < end) {
int mid = start + (end - start) / 2;
if (isEmptyRow(image, mid)) {
end = mid;
} else {
start = mid;
}
}
if (isEmptyRow(image, end)) {
return start;
} else {
return end;
}
}
// 确定行是否存在1，必须检查行内所有列，每次调用检查一行，for循环所有列
private boolean isEmptyRow(char[][] image, int row) {
for (int i = 0; i < image[0].length; i++) {
if (image[row][i] == '1') {
return false;
}
}
return true;
}
// 确定列是否存在1，必须检查列内所有行，每次调用检查一列，for循环所有行
private boolean isEmptyColumn(char[][] image, int column) {
for (int j = 0; j < image.length; j++) {
if (image[j][column] == '1') {
return false;
}
}
return true;
}
}
易错点：
记得-1和+1
-
每个方法的while循环结束后，检查项的return别写错
if (isEmptyRow(image, start)) { return end; }而不是return start； 列在变行不变的时候用列检查判断，行在变列不变的时候用行检查判断(此处容易懵逼)
在方法的while循环结束后对start和end进行检查时，检查顺序是有要求的，如本题实际上是求矩形面积，则应先检查最外侧的点，左边先检查start，右边先检查end，上边先检查start，下边先检查end，因为若出现一模一样的start和end则不同的检查顺序会出现不同的结果
