The Python Program: square.py
1
2
3
4
5
6 import math, string, sys
7
8
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
14
15
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)