黒いピクセルポイントを包む最小の長方形
2199 ワード
http://www.lintcode.com/zh-cn/problem/smallest-rectangle-enclosing-black-pixels/
public class Solution {
/**
* @param image: a binary matrix with '0' and '1'
* @param x: the location of one of the black pixels
* @param y: the location of one of the black pixels
* @return: an integer
*/
public int minArea(char[][] image, int x, int y) {
// write your code here
//
//
int left = 0;
while (true) {
boolean has1 = false;
for (int i = 0; i < image.length; i++) {
if (image[i][left] == '1') {
has1 = true;
break;
}
}
if (has1) {
break;
} else {
left++;
}
}
//
char[] chars = image[0];
int right = chars.length - 1;
while (true) {
boolean has1 = false;
for (int i = 0; i < image.length; i++) {
if (image[i][right] == '1') {
has1 = true;
break;
}
}
if (has1) {
break;
} else {
right--;
}
}
int top = 0;
while (true) {
boolean has1 = false;
for (int i = 0; i < chars.length; i++) {
if (image[top][i] == '1') {
has1 = true;
break;
}
}
if (has1) {
break;
} else {
top++;
}
}
int bottom = image.length - 1;
while (true) {
boolean has1 = false;
for (int i = 0; i < chars.length; i++) {
if (image[bottom][i] == '1') {
has1 = true;
break;
}
}
if (has1) {
break;
} else {
bottom--;
}
}
return (right - left + 1) * (bottom - top + 1);
}
}