CareerCup

Algorithm : Iterate over the rows in O(num_row^2) and go through only the col indexes which differs by row indexes. If all are zero, increment the result.

def numberofSquares(matrix):

	res, idx= 0,0 

	for row1_idx, row1 in enumerate(matrix):
		for row_2idx,row2 in enumerate(matrix[first_row_idx+1:]):
			for col1_idx in range(0,len(matrix[0])):
				col2_idx = col_idx + (row2_idx-row1_idx)
				if (col2_idx < len(matrix[0]) and 
					not row1[col1_idx] and not row1[col2_idx] 
					not row2[col1_idx] and not row2[col2_idx]):
					res += 1

	return res

@DyingLizard, it looks like your solution assume
010
110
000
is a 3x3 square. Did I misunderstand your code?

bool check(bool mat[][4], int size, int srow, int scol, int h)
{
	for (int i = srow; i < srow + h; i++)
		for (int j = scol; j < scol + h; j++)
			if (mat[i][j] == 1)
				return 0;
	return 1;
}

int countZeroSq(bool mat[][4], int size, int srow, int scol, int h)
{
	if (srow == size - 1 || scol == size - 1|| srow + h > size || scol + h > size)	
		return 0;
	int count = 0;
	if (check(mat, size, srow, scol, h))
	{
		if (h > 1)
			count++;
		count += countZeroSq(mat, size, srow, scol, h + 1);
	}
	return count;
}

int countZeroSq(bool mat[][4], int size)
{
	int count = 0;
	for (int i = 0; i < size; i++)
	{
		for (int j = 0; j < size; j++)
		{
			if(mat[i][j] == 0)
				count += countZeroSq(mat, size, i, j, 1);
		}
	}
	return count;

}