Question:
Find the biggest black square from an N*N matrix of squares. 1 means it’s black, 0 means it’s white. Output should be the list of squares which forms the largest black square.
Input : ‘{0#1#1#1#0#1#0#1,1#0#1#0#0#0#0#1,0#0#0#1#0#1#0#0,1#1#1#1#1#0#0#1,1#1#1#1#0#1#1#1,1#1#1#1#0#1#1#1,1#1#1#1#1#1#1#1,1#1#0#1#0#0#1#1}’
Output : {(3#0,3#1,3#2,3#3),(4#0,4#1,4#2,4#3),(5#0,5#1,5#2,5#3),(6#0,6#1,6#2,6#3)}
Solution(Python):
# Author : Sreejith Sreekantan
# Description :
# Find the biggest black square from an N*N matrix of squares. 1 means it's black, 0 means it's white
# Input : '{0#1#1#1#0#1#0#1,1#0#1#0#0#0#0#1,0#0#0#1#0#1#0#0,1#1#1#1#1#0#0#1,1#1#1#1#0#1#1#1,1#1#1#1#0#1#1#1,1#1#1#1#1#1#1#1,1#1#0#1#0#0#1#1}'
# Output : {(3#0,3#1,3#2,3#3),(4#0,4#1,4#2,4#3),(5#0,5#1,5#2,5#3),(6#0,6#1,6#2,6#3)}
#!/usr/bin/python
def largestSquareAt(sq, i, j, k=1):
if not ( i+k<len(sq) and="" j+k<len(sq[i])="" ):="" ="" ="" return="" 0="" for="" x="" in="" range(0,k):="" if="" sq[i+x][j+k-1]="='0':" y="" sq[i+k-1][j+y]="='0':" 1="" +="" largestsquareat(sq,="" i,="" j,="" k+1) ="" ="" def="" biggestsquare(input1):="" len(input1)="=0" or="" not="" (="" input1.count('{')="=input1.count('}')" )="" :="" ''="" i="str(input1)" j="i" for="" j]="" resx="-1" rexy="-1" ressize="-1" res="[]" range(0,len(j)):="" res.append([])="" range(0,len(j[x])):="" res[x].append(largestsquareat(j,="" x,="" y))="" ressize<res[x][y]:="" resy="y" resstring="" ressize="">0:
resstring = "{"
for x in range(resx,resx+ressize):
if x>resx:
resstring += ","
resstring += "("
for y in range(resy,resy+ressize):
if y>resy:
resstring += ","
resstring += (str(x)+"#"+str(y))
resstring += ")"
resstring += "}"
return resstring
input = '{0#1#1#0,0#1#1#1,0#1#1#1,1#1#1#1}'
input1 = '{0#1#1#1#0#1#0#1,1#0#1#0#0#0#0#1,0#0#0#1#0#1#0#0,1#1#1#1#1#0#0#1,1#1#1#1#0#1#1#1,1#1#1#1#0#1#1#1,1#1#1#1#1#1#1#1,1#1#0#1#0#0#1#1}'
input2 = '{0#1#1#1#0#1#0#1,1#0#1#0#0#0#0#1,0#0#0#1#0#1#0#0,1#1#1#1#1#0#0#1,1#1#0#1#0#1#1#1,1#1#1#1#0#1#1#1,1#1#1#1#1#1#1#1,1#1#0#1#0#0#1#1}'
input3= '{0#1#1#1#0#1#0#1,1#0#1#0#0#0#0#1,0#0#0#1#0#1#0#0,1#1#1#1#1#0#0#1,0#1#0#1#0#1#1#1,1#1#1#1#0#1#1#1,1#1#1#1#1#1#1#1,1#1#0#1#0#0#1#1}'
input4 = '{0#0#0#0,0#0#0#0,0#0#0#0,0#0#0#0}'
print biggestSquare('')
print biggestSquare(input1)
print biggestSquare(input2)
print biggestSquare(input3)
print biggestSquare(input4)
WikiSree 