Write a program or function that takes in a multiline string of 0
's and 1
's. No other characters will be in the string and the string will always be rectangular (all lines will have same number of characters), with dimensions as small as 1×1, but otherwise the 0
's and 1
's may be arranged arbitrarily.
You may assume the string has an optional trailing newline, and if desired you may use any two distinct printable ASCII characters in place of 0
and 1
.
Print or return a truthy value if all of the path connected regions of both 0
's and 1
's in the string are solid rectangles, else output a falsy value.
A path connected region of 0
's means that from any one 0
in the region, all the other 0
's can be reached by only moving up, down, left and right to other 0
's (and not moving diagonally, not moving to any 1
, and not moving outside the string bounds). The same idea applies to 1
path connected regions.
A solid rectangle of 0
's means the entire area of the rectangle is filled with 0
's and no 1
's. The same idea applies to 1
solid rectangles.
The shortest code in bytes wins. Tiebreaker is earlier answer.
(Note that the string does not wrap around with toroidal boundary conditions.)
Examples
1) This input string has 3 path connected regions (2 for 0
and 1 for 1
). Only the bottom right 00
region is a solid rectangle though, so the output would be falsy.
0011
0111
0100
2) This input string has 4 path connected regions (2 for both 0
and 1
). All of them are solid rectangles so the output would be truthy.
0011
0011
1100
3) This input has 2 path connected regions, but only one of them is a solid rectangle, so the output would be falsy.
00000000
01111110
00000000
4) This input has only 1 path connected region and is trivially a solid rectangle, so the output is truthy.
11111111
11111111
11111111
Test Cases
A T
just below the input string means truthy, F
means falsy.
0
T
1
T
00
T
01
T
10
T
11
T
0000000
T
1111111
T
011100100100101100110100100100101010100011100101
T
00
11
T
01
10
T
01
11
F
00
01
F
11
11
T
110
100
F
111
000
T
111
101
111
F
101
010
101
T
1101
0010
1101
0010
T
1101
0010
1111
0010
F
0011
0111
0100
F
0011
0011
1100
T
00000000
01111110
00000000
F
11111111
11111111
11111111
T
0000001111
0000001111
T
0000001111
0000011111
F
0000001111
1000001111
F
1000001111
1000001111
T
1110100110101010110100010111011101000101111
1010100100101010100100010101010101100101000
1110100110010010110101010111010101010101011
1010100100101010010101010110010101001101001
1010110110101010110111110101011101000101111
F