package demo;

public class P63 {
//要求在值为0或1、N*N的矩阵中，找到最大的1构成的正方形边框，并返回边长
public static void main(String[] args) {
int[][] arr= {
{0,0,1,0},
{0,1,1,0},
{0,1,1,0},
{0,0,1,0},
};
System.out.println(square(arr,4));
}

static int square(int[][] arr, int N) {
	int n = N;
	int row;
	int col;
	while (n > 0) {
		for (int i = 0; i <= N - n; i++) {
			next: for (int j = 0; j <= N - n; j++) { // 所有可能成立的左上顶点，在i行j列
				if (arr[i][j] == 0)
					continue next;
				row = i;
				col = j;
				// 上边
				while (col <= j + n - 1) {
					if (arr[row][col++] == 0)
						continue next;
				}
				col--;
				// 右边
				while (row <= i + n - 1) {
					if (arr[row++][col] == 0)
						continue next;
				}
				row--;
				// 下边
				while (col >= j) {
					if (arr[row][col--] == 0)
						continue next;
				}
				col++;
				// 左边
				while (row >= i) {
					if (arr[row--][col] == 0)
						continue next;
				}
				row++;

				return n;
			}
		}
		n--;
	}
	return -1;		//没有任何边框
}

}