tioj-1097 . F.營地
tioj1097題序
leetcode題序
定義
定義 dp[i][j] 為以索引(i,j)方格為正方形右下角所形成的最大正方形邊長
轉移方式
$dp(i,j)=min(dp(i−1,j),dp(i−1,j−1),dp(i,j−1))+1$
看一個格字是否可以構成更大的正方形，要以它上方、左方、左上方的格子來決定（左、左上、上跟它自己剛好可以構成一個正方形）
邊界條件
初始化為題目給定的0與1（0代表不能放、1表示可以放）
程式碼
leetcode 221
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int row = matrix.size(),col = matrix[0].size(),ans = 0;;
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
matrix[i][j]-='0';
if(matrix[i][j]==1&& ans ==0)ans = 1;
if(i==0||j==0)continue;
if(matrix[i][j]==1){
matrix[i][j] = min(min(matrix[i-1][j],matrix[i][j-1]),
matrix[i-1][j-1])+1;
ans = max((int)matrix[i][j],ans);
}
}
}
return ans*ans;
}
};
|
tioj 1097
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
| #include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define int long long
using namespace std;
int L,W,dp[2][5005],ans;
void input(int ind){
for(int k=0;k<W;k++){
int temp;
cin>>temp;
if(temp == 2)dp[ind][k] = 0;
else dp[ind][k] = 1;
if(dp[ind][k]==1&&ans == 0)ans = 1;
}
}
signed main(){
ios;
while(cin>>L>>W){
ans = 0;
if(L==0 && W==0)break;
input(0);
for(int i=0;i<L-1;i++){
input(1);
for(int j=1;j<W;j++){
if(dp[1][j]==1){
dp[1][j] = min(dp[0][j],min(dp[0][j-1],dp[1][j-1]))+1;
ans = max(ans,dp[1][j]);
}
}
for(int i=0;i<W;i++)dp[0][i] = dp[1][i];
}
cout<<ans*ans<<endl;
}
}
|
複雜度
實作遇到的一些問題：
- 陣列直接開空間複雜度會爆掉，所以要用到滾動DP （不然會MLE）
- 當i=0 與j=0 時會被忽略掉，如果只有在i=0 或j=0 出現1而其他都是0（不能放）的時候，就會出現答案為0的情況，在輸入時就要做修正
- 因為使用了滾動DP，所以在一開始會先輸入第一排，這時總共剩下L-1排，所以在第24行要是L-1次，才不會需要多輸入一行。