Sunday, March 22, 2015

Largest subsquare


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. 

There is no trick in this problem: no fancy algorithms, just patience. Start from the first column, if there are consecutive m 1s (black pixels), we check each of them to see if they can form a square, if they are, we update the maxLength.
Since we start from the left side of the matrix, the current column we are checking will always be the left bound of the potential square, so the maximum column we need to check is N - maxLength.

public class LargestSubsquare {
 public static int largestSubsquare(int[][] matrix){
  if(matrix == null || matrix.length == 0 || matrix[0].length == 0)
   return 0;
  int row  = 0;
  int col = 0;
  int maxLength = 0;
  int N = matrix.length;
  while(col <= N - maxLength){
   row = 0;
   while(row < N){
    if(row < N && matrix[row++][col] != 1)
     continue;
    int index_r = row;
    while(index_r < N && matrix[index_r][col] == 1){
     int length = index_r - row + 1;
     if(isSquare(matrix, row, col, length))
      maxLength = length;
     index_r++;
    }
    row = index_r; 
   }
   col++;
  }
  return maxLength * maxLength;
 }
 private static boolean isSquare(int[][] matrix, int row, int col, int length){
  for(int j = col; j < length + col; j++){
   if(matrix[row][j] != 1)
    return false;
  }
  for(int i = row; i < length + row; i++){
   if(matrix[i][length + col - 1] != 1)
    return false;
  }
  for(int j = col; j < length + col; j++){
   if(matrix[length + row - 1][j] != 1)
    return false;
  }
  return true;
 }
 public static void main(String[] args) {
  int N = 5;
  int[][] matrix = new int[N][N];
  matrix[0][0] = 0;
  matrix[0][1] = 1;
  matrix[0][2] = 1;
  matrix[0][3] = 0;
  matrix[0][4] = 0;
  matrix[1][0] = 1;
  matrix[1][1] = 1;
  matrix[1][2] = 1;
  matrix[1][3] = 1;
  matrix[1][4] = 1;
  matrix[2][0] = 1;
  matrix[2][1] = 0;
  matrix[2][2] = 1;
  matrix[2][3] = 0;
  matrix[2][4] = 1;
  matrix[3][0] = 0;
  matrix[3][1] = 1;
  matrix[3][2] = 1;
  matrix[3][3] = 1;
  matrix[3][4] = 1;
  matrix[4][0] = 1;
  matrix[4][1] = 1;
  matrix[4][2] = 0;
  matrix[4][3] = 0;
  matrix[4][4] = 0;  
  System.out.println(largestSubsquare(matrix));
 }
}

No comments:

Post a Comment