给定一个方阵，其中每个单元(像素)非黑即白。设计一个算法，找出 4 条边皆为黑色像素的最大子方阵。
返回一个数组 [r, c, size] ，其中 r, c 分别代表子方阵左上角的行号和列号，size 是子方阵的边长。若有多个满足条件的子方阵，返回 r 最小的，若 r 相同，返回 c 最小的子方阵。若无满足条件的子方阵，返回空数组。
示例 1
解释: 输入中 0 代表黑色，1 代表白色，标粗的元素即为满足条件的最大子方阵
示例2
关键词：leetcode，异或运算，矩阵，数组
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class ostt {
private int global_row, global_col;
private int[][] global_matrix;
private static int[]res =new int[3];
public int[] findSquare(int[][] matrix) {
global_matrix = matrix;
if ((global_row = matrix.length) <1) return new int[0];
global_col = matrix[0].length;
for (int i =0; i < global_row -res[2]; ++i)
and_operate(i);
return res[2] >0 ?res :new int[0];
}
private void and_operate(int cur_idx) {
int[] first_row =global_matrix[cur_idx], base = first_row.clone();
if (res[2] <1)
for (int i =0; i < global_col; ++i)
if (first_row[i] <1) {
res[2] =1;
res[0] = cur_idx;
res[1] = i;
break;
}
int offset =0;
for (int i = cur_idx +1; i < global_row; ++i) {
++offset;
int[] last_row =global_matrix[i];
for (int j =0; j < global_col; ++j)
base[j] |=global_matrix[i][j];
List idx_list =new ArrayList<>();
int count =0, temp_idx =0;
for (; temp_idx < global_col - offset; ++temp_idx) {
if (base[temp_idx] ==0) {
++count;
if (base[temp_idx + offset] ==0)
idx_list.add(temp_idx);
}
}
if (count <2) {
for (; temp_idx < global_col; ++temp_idx)
if (base[temp_idx] ==0 && ++count ==2)
break;
if (count <2)
return;
}
for (int begin_idx : idx_list) {
int end_idx = begin_idx + offset;
for (int l = begin_idx +1; l < end_idx; ++l)
if (first_row[l] >0 || last_row[l] >0)
continue;
if (res[2] < offset +1) {
res[2] = offset +1;
res[0] = cur_idx;
res[1] = begin_idx;
}
}
}
}
public static void main(String[] args){
int matrix[][]={{0,1,1},{1,0,1},{1,1,0}};
ostt osfs =new ostt();
osfs.findSquare(matrix);
System.out.println(Arrays.toString(res));
}
}
网友评论