Hi everyone! Here’s a fun problem: Construct an n*m binary matrix such that all the 1-cells form a single 4-connected component, while maximizing the number of 4-connected components formed by the 0-cells. Two cells are considered adjacent if they share an edge. Is there an O(nm) construction with a provably tight upper bound on the number of zero-components? What is the tightest upper bound you can establish, and what are the best achievable time and space complexities for the construction?
note: remember to handle n=1 or m=1
(btw im editing so much lol)
my construction (
0: .and1: #):its $$$\lceil n/2 \rceil \cdot \lceil m/2 \rceil$$$ 0 components
time and space is $$$O(nm)$$$