CareerCup

import java.util.*;

public class BinaryMatrix {
	class Square {
		int size;
		int r1;
		int r2;
		int c1;
		int c2;
		
		public Square(int x1, int x2, int y1, int y2) {
			r1 = x1; r2 = x2;
			c1 = y1; c2 = y2;
			size = (r2-r1+1)*(c2-c1+1);
		}
		
		public String toString() {
			String s;
			if (size == 1) s = "{" + r1 + "," + c1 + "}";
			else s = "{" + r1 + "," + r2 + "," + c1 + "," + c2 + "}";
			return s;
		}
	}

	protected int[][] a;
	int rows;
	int cols;
	
	public BinaryMatrix(int r, int c) {
		rows = r;
		cols = c;
		a = new int[r][c];
		initMatrix();
	}
	
	protected void initMatrix() {
		Random r = new Random();
		for (int i=0; i<rows; i++) {
			for (int j=0; j<cols; j++) {
				a[i][j] = r.nextInt(2);
			}
		}
	}
	
	public void dumpMatrix() {
		for (int i=0; i<rows; i++) {
			for (int j=0; j<cols; j++) {
				System.out.print(a[i][j]);
			}
			System.out.println();
		}
	}
	
	public List<Square> getSquares() {
		List<Square> sqlist = new LinkedList<Square>();
		for (int i=0; i<rows; i++) {
			int s = -1; 
			int j = 0;
			while (true) {
				if (j >= cols) {
					if (s != -1) addSquare(sqlist, i, s, j-1);
					break;
				}
				if (a[i][j] == 1) {
					if (s == -1) { s = j++; continue; } 
					if (isSquare(i, s, j)) {
						j++;
						continue;
					}
					addSquare(sqlist, i, s, j-1);
					j = s+1;
					s = -1;
				} else {
					if (s != -1) {
						addSquare(sqlist, i, s, j-1);
						s = -1;
					}
					j++;
				}
			}
		}
		
		return sqlist;
	}

	public void addSquare(List<Square> sqlist, int row, int c1, int c2) {
		Square sq = new Square(row, row+(c2-c1), c1, c2);
		if (isValidSquare(sqlist, sq)) {
			sqlist.add(sq);
		}
	}

	public boolean isSquare(int row, int c1, int c2) {
		// 1. single cell is a square
		if (c1 == c2) return true;
		// 2. assume row, c1, c2-1 is square, now check if row, c1, c2 is a square
		int d = c2 - c1;
		if (row + d >= rows) return false;
		for (int i=1; i<d; i++) {
			if (a[row+i][c2] != 1) return false;
		}
		for (int j=c1; j<=c2; j++) {
			if (a[row+d][j] != 1) return false;
		}
		return true;
	}
	
	public boolean isValidSquare(List<Square> sqlist, Square sq) {
		//if (sq.size ==1 ) return false;
		for (Square s : sqlist) {
			if (sq.size < s.size) {
				if (sq.r1 >= s.r1 && sq.r2 <= s.r2 && sq.c1 >= s.c1 && sq.c2 <= s.c2) return false; 
			}
		}
		return true;
	}

	public static void main(String[] args) {
		BinaryMatrix b = new BinaryMatrix(8, 10);
		b.dumpMatrix();
		List<Square> sqs = b.getSquares();
		System.out.println(sqs);
	}

}

0110000111
0000010111
1101111110
0010010111
1100010011
1110011010
1110100100
0111111000
[{0,1}, {0,2}, {0,1,7,8}, {0,1,8,9}, {1,5}, {1,2,7,8}, {2,0}, {2,1}, {2,3}, {2,4}, {2,5}, {2,6}, {2,3,7,8}, {3,2}, {3,5}, {3,4,8,9}, {4,5,0,1}, {4,5}, {5,6,0,1}, {5,6,1,2}, {5,5}, {5,6}, {5,8}, {6,7,1,2}, {6,4}, {6,7}, {7,3}, {7,4}, {7,5}, {7,6}]

this is a modification of "Maximum size square sub-matrix with all 1s" DP problem
from www dot geeksforgeeks.org/archives/6257

In the pseudocode, S[i][j] is a size of the maximum square submatrix with all 1s with bottom-right corner (i;j). After computing S[i][j], we only need to remove those squares which are completely contained in large squares

#define R 6
#define C 5

int S[R][C];
int M[R][C] =  {
    {0, 1, 1, 0, 1},
    {1, 1, 0, 1, 0},
    {0, 1, 1, 1, 0},
    {1, 1, 1, 1, 0},
    {1, 1, 1, 1, 1},
    {0, 0, 0, 0, 0}};

void fillin(int r1, int c1) { // mark overlapping squares
    int sz = S[r1][c1], i, j;
    int r0 = r1 - sz + 1, c0 = c1 - sz + 1;
    for(i = r0; i <= r1; i++)
    for(j = c0; j <= c1; j++) {
        int s = S[i][j];
        if(i - s + 1 >= r0 && j - s + 1 >= c0)
           S[i][j] = 0;
    }
}

void printMaxSubSquare()
{
  int i,j;
  int max_of_s, max_i, max_j;
  /* Set first column of S[][]*/
  for(i = 0; i < R; i++)
     S[i][0] = M[i][0];
  /* Set first row of S[][]*/
  for(j = 0; j < C; j++)
     S[0][j] = M[0][j];
  /* Construct other entries of S[][]*/
  for(i = 1; i < R; i++)
  {
    for(j = 1; j < C; j++)
    {
      if(M[i][j] == 1)
        S[i][j] = std::min(std::min(S[i][j-1], S[i-1][j]), S[i-1][j-1]) + 1;
      else
        S[i][j] = 0;
    }
  }
    printf("Input:\n");
      for(i = 0; i < R; i++) {
    for(j = 0; j < C; j++) {
        printf("%d ", M[i][j]);
    }
    printf("\n\n");
    }
    int cnt = 0;
    for(i = R-1; i >= 0; i--)
    for(j = C-1; j >= 0; j--) {
        if(S[i][j] <= 0)
            continue;
        printf("%d: size: %d; bottom-right: (%d; %d)\n", ++cnt, S[i][j], i, j);
        fillin(i, j);
    }
    printf("\n");
}

int main()  {
   printMaxSubSquare();
}

some results:
Input:
1 1 0 0 1
1 1 1 1 0
1 1 0 1 1
1 1 0 0 1

1: size: 1; bottom-right: (3; 4)
2: size: 2; bottom-right: (3; 1)
3: size: 1; bottom-right: (2; 4)
4: size: 1; bottom-right: (2; 3)
5: size: 2; bottom-right: (2; 1)
6: size: 1; bottom-right: (1; 3)
7: size: 1; bottom-right: (1; 2)
8: size: 2; bottom-right: (1; 1)
9: size: 1; bottom-right: (0; 4)


Input:
0 1 1 0 1
1 1 0 1 0
0 1 1 1 0
1 1 1 1 0
1 1 1 1 1
0 0 0 0 0

1: size: 1; bottom-right: (4; 4)
2: size: 3; bottom-right: (4; 3)
3: size: 2; bottom-right: (4; 1)
4: size: 1; bottom-right: (1; 3)
5: size: 1; bottom-right: (1; 1)
6: size: 1; bottom-right: (1; 0)
7: size: 1; bottom-right: (0; 4)
8: size: 1; bottom-right: (0; 2)
9: size: 1; bottom-right: (0; 1)

hi, i want to made this program using Thread Pools. where should i change?

Bhavesh Jogi