学步园

题目

原文：

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 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;
	int currentMaxSize = 0;
	Subsquare sq = null;
	int col = 0;

	// Iterate through each column from left to right
	while (N - col > currentMaxSize) { // See step 4 above
		for (int row = 0; row < matrix.length; row++){
			// starting from the biggest
			int size = N - Math.max(row, col);
			while (size > currentMaxSize){
				if (isSquare(matrix, row, col, size)){
					currentMaxSize = size;
					sq = new Subsquare(row, col, size);
					break; // go to next (full) column
				}
				size--;
			}
		}
		col++;
	}
	return sq;
}

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;
}

public class Subsquare {
	public int row, column, size;
	public Subsquare(int r, int c, int sz) {
		row = r;
		column = c;
		size = sz;
	}
}

---EOF---