## Saturday, July 9, 2016

### Max Square Matrix

http://www.hawstein.com/posts/20.11.html
Imagine you have a square matrix, where each cell is filled with either black or white. Design an algorithm to find the maximum subsquare such that all four borders are filled with black pixels.

## 解答

public class SquareCell {
public int zerosRight = 0;
public int zerosBelow = 0;
public SquareCell(int right, int below) {
zerosRight = right;
zerosBelow = below;
}
}
public class Subsquare {
public int row, column, size;
public Subsquare(int r, int c, int sz) {
row = r;
column = c;
size = sz;
}
}

public static Subsquare findSquareWithSize(SquareCell[][] processed, int square_size) {
// On an edge of length N, there are (N - sz + 1) squares of length sz.
int count = processed.length - square_size + 1;
// Iterate through all squares with side length square_size.
for (int row = 0; row < count; row++) {
for (int col = 0; col < count; col++) {
if (isSquare(processed, row, col, square_size)) {
return new Subsquare(row, col, square_size);
}
}
}
return null;
}

public static Subsquare findSquare(int[][] matrix){
assert(matrix.length > 0);
for (int row = 0; row < matrix.length; row++){
assert(matrix[row].length == matrix.length);
}
SquareCell[][] processed = processSquare(matrix);
int N = matrix.length;
for (int i = N; i >= 1; i--) {
Subsquare square = findSquareWithSize(processed, i);
if (square != null) {
return square;
}
}
return null;
}

private static boolean isSquare(SquareCell[][] matrix, int row, int col, int size) {
SquareCell topLeft = matrix[row][col];
SquareCell topRight = matrix[row][col + size - 1];
SquareCell bottomRight = matrix[row + size - 1][col];
if (topLeft.zerosRight < size) { // Check top edge
return false;
}
if (topLeft.zerosBelow < size) { // Check left edge
return false;
}
if (topRight.zerosBelow < size) { // Check right edge
return false;
}
if (bottomRight.zerosRight < size) { // Check bottom edge
return false;
}
return true;
}

public static SquareCell[][] processSquare(int[][] matrix) {
SquareCell[][] processed = new SquareCell[matrix.length][matrix.length];
for (int r = matrix.length - 1; r >= 0; r--) {
for (int c = matrix.length - 1; c >= 0; c--) {
int rightZeros = 0;
int belowZeros = 0;
if (matrix[r][c] == 0) { // only need to process if it's a black cell
rightZeros++;
belowZeros++;
if (c + 1 < matrix.length) { // next column over is on same row
SquareCell previous = processed[r][c + 1];
rightZeros += previous.zerosRight;
}
if (r + 1 < matrix.length) {
SquareCell previous = processed[r + 1][c];
belowZeros += previous.zerosBelow;
}
}
processed[r][c] = new SquareCell(rightZeros, belowZeros);
}
}
return processed;
}

public static Subsquare findSquareWithSize(int[][] matrix, int squareSize) {
// On an edge of length N, there are (N - sz + 1) squares of length sz.
int count = matrix.length - squareSize + 1;
// Iterate through all squares with side length square_size.
for (int row = 0; row < count; row++) {
for (int col = 0; col < count; col++) {
if (isSquare(matrix, row, col, squareSize)) {
return new Subsquare(row, col, squareSize);
}
}
}
return null;
}

public static Subsquare findSquare(int[][] matrix){
assert(matrix.length > 0);
for (int row = 0; row < matrix.length; row++){
assert(matrix[row].length == matrix.length);
}
int N = matrix.length;
for (int i = N; i >= 1; i--) {
Subsquare square = findSquareWithSize(matrix, i);
if (square != null) {
return square;
}
}
return null;
}

private static boolean isSquare(int[][] matrix, int row, int col, int size) {
// Check top and bottom border.
for (int j = 0; j < size; j++){
if (matrix[row][col+j] == 1) {
return false;
}
if (matrix[row+size-1][col+j] == 1) {
return false;
}
}
// Check left and right border.
for (int i = 1; i < size - 1; i++) {
if (matrix[row+i][col] == 1){
return false;
}
if (matrix[row+i][col+size-1] == 1) {
return false;
}
}
return true;
}