blob: 760041916ebbd43fa822cff9b65a3c903d97ea69 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
#!/usr/bin/env python3
# Challenge 084
#
# TASK #2 > Find Square
# Submitted by: Mohammad S Anwar
# You are given matrix of size m x n with only 1 and 0.
#
# Write a script to find the count of squares having all four corners set as 1.
#
# Example 1:
# Input: [ 0 1 0 1 ]
# [ 0 0 1 0 ]
# [ 1 1 0 1 ]
# [ 1 0 0 1 ]
#
# Output: 1
# Explanation:
# There is one square (3x3) in the given matrix with four corners as 1 starts
# at r=1;c=2.
# [ 1 0 1 ]
# [ 0 1 0 ]
# [ 1 0 1 ]
# Example 2:
# Input: [ 1 1 0 1 ]
# [ 1 1 0 0 ]
# [ 0 1 1 1 ]
# [ 1 0 1 1 ]
#
# Output: 4
# Explanation:
# There is one square (4x4) in the given matrix with four corners as 1 starts
# at r=1;c=1.
# There is one square (3x3) in the given matrix with four corners as 1 starts
# at r=1;c=2.
# There are two squares (2x2) in the given matrix with four corners as 1.
# First starts at r=1;c=1 and second starts at r=3;c=3.
# Example 3:
# Input: [ 0 1 0 1 ]
# [ 1 0 1 0 ]
# [ 0 1 0 0 ]
# [ 1 0 0 1 ]
#
# Output: 0
import fileinput
import re
def read_input():
lines = []
for line in fileinput.input():
lines.append(line)
return lines
def read_matrix(lines):
m = []
for line in lines:
line = re.sub(r"\D+", " ", line)
cols = [int(x) for x in line.split()]
m.append(cols)
return m
def count_squares(m):
nrows = len(m)
ncols = len(m[0])
if nrows < 2 or ncols < 2:
return 0
count = 0
for r in range(nrows):
for c in range(ncols):
if m[r][c]:
d = 1
while r+d < nrows and c+d < ncols:
if m[r+d][c] and m[r][c+d] and m[r+d][c+d]:
count += 1
d += 1
return count
print(count_squares(read_matrix(read_input())))
|
