Find max subsquare whose border values are all 1

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.

Thoughts:
We are going to scan column by column, checking to see if this column can be the left-border of the desired subsquare. Along each column, we build “sliding windows”, from large size to small size. The size of the window is the size of the subsquare. The winodw starts at different row, moving from top to bottom. When the window is fixed in a position, we chan check if this subsquare is valid or not. If so, we update the max subsquare we have found then continue.

Example:
111
011
000

  1. 1st column:
    1. 1st row: window size = 3: {{1,1,1,},{0,1,1},{0,0,0}} is not valid; window size = 2: {{1,1,},{0,1}} is not valid; window size = 1: {{1}} is valid, so update it.
    2. 2nd row: window size = 2: {{0,1},{0,0}} is not valid; window size = 1: no need to check. already have a current max subsquare with size 1.
  2. 2nd column:
    1. 1st row: window size = 2: {{1,1},{1,1}} is valid, so update it; window size = 1: no need to check.
    2. 2nd row: no need to check. Max subsquare can be found is of size 2, but we already have a valid one with size 2.
  3. 3rd column:No need to check.

Codes:

	public static int[][] findMaxSubsquare(int[][] square) {
		int[][] maxSubsquare = null;
		int maxSize = 0;
		for (int col = 0; square.length - col > maxSize; ++col) {
			for (int row = 0; square.length - row > maxSize; ++row) {
				for (int size = square.length - Math.max(row, col); 
							size > maxSize; --size) {
					if (isValidSubsquare(square, row, col, size)) {
						maxSize = size;
						maxSubsquare = new int[size][size];
						for (int i = row; i < size + row; ++i)
							System.arraycopy(square[i], col, maxSubsquare[i
									- row], 0, size);
					}
				}
			}
		}
		return maxSubsquare;
	}

	private static boolean isValidSubsquare(int[][] square, int row, int col,
			int size) {
		// up and bottom border
		for (int j = col; j < col + size; ++j) {
			if (square[row][j] == 0)
				return false;
			if (square[row + size - 1][j] == 0)
				return false;
		}
		// left and right border
		for (int i = row; i < row + size; ++i) {
			if (square[i][col] == 0)
				return false;
			if (square[i][col + size - 1] == 0)
				return false;
		}
		return true;
	}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: