The Python Program: square.py

  1 #
  2 #  SER 2010.  Problem E:  Maximum Square
  3 #  Author: Ryan Stansifer
  4 #
  5 
  6 import math, string, sys
  7 
  8 # for each data set 1,2,...
  9 while True:
 10    (n,m) = map (int, string.split (sys.stdin.readline())[0:2]);
 11    if n==0 or m==0: break
 12 
 13    # Make room in two dimension array
 14    # AVOID:   square = [[0]*m]*n
 15    # as it makes shallow copy
 16    square = [[0 for c in range(m)] for r in range(n)]
 17 
 18    mx = 0;
 19    for r in range(n):
 20       row = map (int, string.split (sys.stdin.readline())[0:m]);
 21       for c in range(m):
 22         assert row[c]==0 or row[c]==1
 23         if r==0 or c==0 or row[c]==0 or square[r-1][c]==0 or square[r][c-1]==0:
 24            square[r][c] = row[c]
 25         else:
 26            x = min (square[r-1][c], square [r][c-1])
 27            square[r][c] = x if square[r-x][c-x]==0 else x+1
 28 
 29         if square[r][c]>mx:
 30            mx = square[r][r]
 31 
 32    sys.stdout.write ("%d\n" % mx)