Given a matrix (H × W) which contains only 1 and 0, find the area of the largest square…
- User
Given a matrix (H × W) which contains only 1 and 0, find the area of the largest square matrix which only contains 0s.
Constraints
- 1 ≤ H, W ≤ 1,400 Input
H W c1,1 c1,2 ... c1,W c2,1 c2,2 ... c2,W : cH,1 cH,2 ... cH,W
In the first line, two integers H and W separated by a space character are given. In the following H lines, ci,j, elements of the H × W matrix, are given.
Output
Print the area (the number of 0s) of the largest square.
Example
Input
4 5 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0
Output
4
Assistant
We are asked: Given a matrix (H x W) which contains only 1 and 0, find the area of the largest square matrix which only contains 0s. Essentially, largest all-zero square submatrix. Output area (side length squared). Constraints: H, W up to 1400, so up to ~2e6 cells. Need O(H*W) solution.
Standard dynamic programming: For each cell (i, j), let dp[i][j] be the side length of the largest square of zeros with bottom-right corner at (i, j). If matrix[i][j] == 1 then dp[i][j] = 0. Else dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1. Answer is max dp squared.
But careful: The area is number of zeros, which is side length squared. So answer = (max_side)^2.
Need to handle boundaries: dp[0][] or dp[][0] = 1 if cell is 0 else 0.
Complexity O(HW). Memory O(W) if we do rolling array, but H, W up to 1400, we could store full 2D array (~2M ints) which is fine. But we can also use rolling to be safe. But given limit 1400, we can allocate 14001400 ints ~ 2 million, each 4 bytes = 8 MB, okay.
Input format: First line H W. Then H lines, each with numbers separated by spaces? Example: "0 0 1 0 0". So we parse.
Edge: Might have spaces, maybe newlines. Use reading.
We need to output area.
So solution: Read H, W. Create a 2D list of ints or bool. Then compute dp. Use 0-indexed.
dp[i][j] for i=0..H-1, j=0..W-1.
Initialize dp as zeros.
For i=0..H-1: for j=0..W-1: if matrix[i][j] == 1: dp[i][j] = 0 else: if i==0 or j==0: dp[i][j] = 1 else: dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
Keep max_side = max(max_side, dp[i][j]).
Then answer = max_side * max_side.
Test with example.
Example matrix: 4 5 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0
Compute: Row0: [0,0,1,0,0] Actually values: (0,0):0 => dp=1; (0,1):0 => dp=1; (0,2):1 =>0; (0,3):0 =>1; (0,4):0 =>1. Row1: [1,0,0,0,0] (1,0):1 =>0 (1,1):0 => i>0 j>0 => min(dp[0][1]=1, dp[1][0]=0, dp[0][0]=1) = 0 +1 =1 => dp=1 (1,2):0 => min(dp[0][2]=0, dp[1][1]=1, dp[0][1]=1) =0+1=1 (1,3):0 => min(dp[0][3]=1, dp[1][2]=1, dp[0][2]=0) =0+1=1 (1,4):0 => min(dp[0][4]=1, dp[1][3]=1, dp[0][3]=1)=1+1=2 => dp=2. So square side 2 => area 4. Row2: [0,0,0,1,0] (2,0):0 => i=0? i=2 j=0 => i>0 j=0 => border? Actually j=0 => border => dp=1 (since i>0 but j==0 so treat as border? rule: if i==0 or j==0, dp=1. So yes dp=1. (2,1):0 => min(dp[1][1]=1, dp[2][0]=1, dp[1][0]=0) =0+1=1 (2,2):0 => min(dp[1][2]=1, dp[2][1]=1, dp[1][1]=1)=1+1=2 => dp=2 (2,3):1 =>0 (2,4):0 => border? j=4 >0, i=2>0 => min(dp[1][4]=2, dp[2][3]=0, dp[1][3]=1) =0+1=1 => dp=1 Row3: [0,0,0,1,0] (3,0):0 => border =>1 (3,1):0 => min(dp[2][1]=1, dp[3][0]=1, dp[2][0]=1)=1+1=2 (3,2):0 => min(dp[2][2]=2, dp[3][1]=2, dp[2][1]=1)=1+1=2? Actually min=1? Let's compute: dp[2][2]=2, dp[3][1]=2, dp[2][1]=1 -> min=1, +1 =2. (3,3):1 =>0 (3,4):0 => min(dp[2][4]=1, dp[3][3]=0, dp[2][3]=0) =0+1=1
Max side=2 => area=4. matches.
Thus DP works.
Now implement.
But wait: The problem statement says "largest square matrix which only contains 0s". It's exactly as we solved. So solution is straightforward.
Now constraints: H, W up to 1400, so O(HW) DP with int operations is fine.
We need to handle input size: reading lines, splitting.
Potential pitfalls: The input might have spaces and newlines; but Python input reading line by line works.
We'll do:
import sys
def main(): data = sys.stdin.read().strip().split() if not data: return it = iter(data) H = int(next(it)) W = int(next(it)) # Create matrix as list of list of ints # We can store as list of rows, each row length W # Or we can compute DP on the fly using previous row only, but need dp of previous row and previous column. Actually we can compute with two rows: current dp row and previous dp row. And also need matrix value. But we can also read matrix rows as we go. However reading all data at once is easier.
# But reading all data and converting to ints: total ints = H*W + 2, which is up to ~2e6+2, fine for memory. # We'll read all ints and fill matrix. # We'll allocate matrix as list of lists. # Actually we might not need to store entire matrix; we can store DP and also need to check cell is 0 or 1. If we read row by row, we can keep that row's values. But DP needs previous dp row. So we can process as we read each row. That's memory efficient. Let's do that. # We'll read the matrix row by row from the iterator. # But we already read all tokens; we can just iterate. # Approach: We'll have prev_dp = [0]*W # cur_dp = [0]*W # max_side = 0 # For i in range(H): # row = [int(next(it)) for _ in range(W)] # for j in range(W): # if row[j] == 1: # cur_dp[j] = 0 # else: # if i == 0 or j == 0: # cur_dp[j] = 1 # else: # cur_dp[j] = min(prev_dp[j], cur_dp[j-1], prev_dp[j-1]) + 1 # if cur_dp[j] > max_side: # max_side = cur_dp[j] # prev_dp, cur_dp = cur_dp, [0]*W (or reuse) # Actually we need to reset cur_dp for next iteration; we can just assign cur_dp = [0]*W after swapping? Simpler: have prev_dp list and for each i compute new_dp list. At end, prev_dp = new_dp. # So: # new_dp = [0]*W # compute... # prev_dp = new_dp # But careful: When we compute cur_dp[j] using cur_dp[j-1] which is the new row's left value, we need to have it computed. So we need to use new_dp list and refer to new_dp[j-1] and prev_dp[j] and prev_dp[j-1]. That works. # Implementation: # Initialize prev_dp as list of zeros. prev_dp = [0] * W max_side = 0 for i in range(H): # read current row values row = [int(next(it)) for _ in range(W)] new_dp = [0] * W for j in range(W): if row[j] == 1: new_dp[j] = 0 else: if i == 0 or j == 0: new_dp[j] = 1 else: # min of left, top, top-left # left: new_dp[j-1] # top: prev_dp[j] # top-left: prev_dp[j-1] new_dp[j] = min(new_dp[j-1], prev_dp[j], prev_dp[j-1]) + 1 if new_dp[j] > max_side: max_side = new_dp[j] prev_dp = new_dp print(max_side * max_side)if name == "main": main()
That's it.
But we must ensure that we correctly handle the case when H=0 or W=0? Constraint says at least 1. So fine.
Double-check: The DP formula for boundaries: if i==0 or j==0, dp=1 if cell==0. That's correct.
Edge: If entire matrix is all ones, max_side remains 0, area = 0. Should we output 0? Largest square with only zeros has side 0, area 0. Is that valid? Probably yes.
Thus solution done.
Now we can add explanation in answer? The user asked "Given a matrix... find the area". So we need to output the answer.
But the conversation context: The user likely expects the solution to be coded. However the instruction says: "You are an AI assistant. ... Provide answer in final channel." Probably just code. However the user wrote: "Given a matrix (H × W) ..." with constraints and input format, and then output. That's a typical problem statement. So we need to output the code (probably in Python) that solves it. Or we could explain approach and provide code. But typical ChatGPT response: Provide solution description and code. But the instruction: "You are an AI assistant. ... Provide answer in final channel." So we should produce the final answer, which is the solution code. Possibly with brief explanation. We can include explanation as comment.
Thus final answer: Python code implementing DP with O(HW) time and O(W) memory.
Let's produce that.
Potential pitfalls: The input may have extra spaces, but reading with sys.stdin.read().split() handles.
Also, we must ensure to convert tokens to int.
We can use sys.stdin.buffer.read() for speed.
Let's write code:
import sys
def main(): data = sys.stdin.buffer.read().split() if not data: return it = iter(data) H = int(next(it)) W = int(next(it)) prev = [0]*W max_side = 0 for i in range(H): cur = [0]*W for j in range(W): val = int(next(it)) if val == 0: if i == 0 or j == 0: cur[j] = 1 else: cur[j] = min(cur[j-1], prev[j], prev[j-1]) + 1 if cur[j] > max_side: max_side = cur[j] # else cur[j] remains 0 prev = cur print(max_side * max_side)
if name == "main": main()
Yes.
We can also incorporate small optimization: we only need to compute dp for zero cells; for ones we skip (default 0). So done.
Now test with given example.
Let's simulate quickly:
Input: "4 5\n0 0 1 0 0\n1 0 0 0 0\n0 0 0 1 0\n0 0 0 1 0\n" Our code reads tokens: ['4','5','0','0','1','0','0','1','0','0','0','0','0','0','0','1','0','0','0','0','1','0']? Actually careful: split on whitespace. So tokens: 4,5,0,0,1,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0,1,0. H=4, W=5, we then read exactly H*W=20 ints from iterator. The loop: i=0, j=0..4 reads first 5: 0,0,1,0,0. Then i=1 reads next 5: 1,0,0,0,0. i=2 reads next 5: 0,0,0,1,0. i=3 reads next 5: 0,0,0,1,0. Works.
dp computation as earlier gives max_side=2 -> print 4.
All good.
Now think about possible large values: side up to min(H,W) <= 1400, area up to 1,960,000 fits in int.
Now potential alternative: Use numpy? Not allowed.
So final answer: Provide code.
But the user might expect a C++ solution? The problem statement doesn't specify language. Usually in many online judges, solutions can be in multiple languages. But as ChatGPT, we can output Python code; it's typical. We could also mention that it's in Python. Since the conversation is in English, we can answer with code and brief explanation. However, the instruction: "You are an AI assistant. ... Provide answer in final channel." In many similar tasks, we output just the code. But to be safe, include explanation in comments.
Thus final output:
import sys def main(): data = sys.stdin.buffer.read().split() if not data: return it = iter(data) H = int(next(it)) W = int(next(it)) prev_dp = [0] * W max_side = 0 for i in range(H): cur_dp = [0] * W for j in range(W): # read cell value val = int(next(it)) if val == 0: if i == 0 or j == 0: cur_dp[j] = 1 else: cur_dp[j] = min(cur_dp[j-1], prev_dp[j], prev_dp[j-1]) + 1 if cur_dp[j] > max_side: max_side = cur_dp[j] # else cur_dp[j] stays 0 prev_dp = cur_dp print(max_side * max_side) if __name__ == "__main__": main()That's final. ```python
import sys
def main() -> None: data = sys.stdin.buffer.read().split() if not data: return it = iter(data) H = int(next(it)) W = int(next(it))
# dp values for the previous row prev_dp = [0] * W max_side = 0 for i in range(H): cur_dp = [0] * W for j in range(W): val = int(next(it)) if val == 0: if i == 0 or j == 0: cur_dp[j] = 1 else: cur_dp[j] = min(cur_dp[j-1], prev_dp[j], prev_dp[j-1]) + 1 if cur_dp[j] > max_side: max_side = cur_dp[j] # otherwise cur_dp[j] stays 0 prev_dp = cur_dp print(max_side * max_side)if name == "main": main()