s142 - 最大正方形

🔗 前往 ZeroJudge 原題

題目描述

題目要求在一個 n x m 的二元矩陣中，找出邊長最大的全為 1 的正方形，並輸出其邊長。矩陣中保證至少有一個 1。

解題思路

本題使用「二維前綴和（2D Prefix Sum）」搭配剪枝來解決。

首先，邊讀取資料邊計算二維前綴和矩陣 dp[i][j]，其中 dp[i][j] 儲存了矩陣中從 (1, 1) 到 (i, j) 的所有元素的總和。有了前綴和，我們就能在 $O(1)$ 時間內快速算出任意矩形區域內的元素和。

對於每個可能的右下角座標 (i, j)，我們不需要從邊長 $1$ 開始檢查。因為目標是尋找「最大」正方形，我們只需關心能否構成比當前最大答案更大的正方形。因此，將搜尋邊長 k 的起點直接設為 ans + 1。

利用前綴和計算該範圍的總和，如果等於 $k \times k$，說明該正方形全為 $1$，我們就更新 ans = k 並繼續檢查更大的邊長。反之，如果連邊長 k 都無法滿足全為 $1$ 的條件，那麼以 (i, j) 為右下角絕對不可能形成更大的正方形，此時直接 break 退出內層迴圈。

複雜度分析

• 時間複雜度：均攤 $O(n \times m)$。表面上程式碼有三層迴圈，但由於變數 ans 是全域單調遞增的，在整個程式執行期間，成功進入 if 條件並使 k 繼續遞增的總次數不超過 $\min(n, m)$ 次。另一方面，進入 else 並觸發 break 提早結束的動作，對於每一個格子 (i, j) 最多只會發生一次。因此最內層迴圈的總執行次數上限為 $n \times m + \min(n, m)$，時間複雜度實際上是優雅的 $O(n \times m)$。
• 空間複雜度：$O(n \times m)$。需要一個二維陣列 dp 來儲存前綴和狀態。

程式碼

#include <iostream>
using namespace std;
int dp[1001][1001], n, m, ans;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			cin >> dp[i][j];
			dp[i][j]+=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
			for(int k=ans+1;k<=min(i, j);++k){
				if(dp[i][j]-dp[i-k][j]-dp[i][j-k]+dp[i-k][j-k]==k*k){
					ans=k;
				}		
				else{
					break;
				}	
			}
		}
	}
	cout << ans;
}