洛谷 P1387 最大正方形 & P2701 [USACO5.3]巨大的牛棚Big Barn (求最大子正方形)

2019-06-11

题目： P1387 最大正方形： https://www.luogu.org/problemnew/show/P1387

　　　 P2701 [USACO5.3]巨大的牛棚Big Barn ： https://www.luogu.org/problemnew/show/P2701

题目均给出一个已知矩阵。

在该已知矩阵中寻找最大的一个子正方形。

方法：DP

转移方程：f[i][j] = min( min( f[i][j-1] , f[i-1][j] ) , f[i-1][j-1] ) + 1

P1387 最大正方形 AC代码：

 1 //
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 typedef long long ll;
 5 #define ri register ll
 6 
 7 ll n,m,k;
 8 ll a[105][105];
 9 ll f[105][105];
10 
11 signed main()
12 {
13     ios::sync_with_stdio(0),cin.tie(0);
14     cin>>n>>m;
15     for(ri i=1;i<=n;i++)
16     {
17         for(ri j=1;j<=m;j++)
18         {
19             cin>>a[i][j];
20             if(a[i][j])
21             {
22                 f[i][j]=min(min(f[i][j-1],f[i-1][j]),f[i-1][j-1])+1;
23             }
24             k=max(k,f[i][j]);
25         }
26     }
27     cout<<k<<'
';
28     return 0;
29 }
30 //

P2701 [USACO5.3]巨大的牛棚Big Barn AC代码：

 1 //
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 typedef long long ll;
 5 #define ri register ll
 6 
 7 ll n,t,k;
 8 bool shu[1005][1005];
 9 ll f[1005][1005];
10 
11 signed main()
12 {
13     ios::sync_with_stdio(0),cin.tie(0);
14     cin>>n>>t;
15     for(ri i=1;i<=t;i++)
16     {
17         ri a,b;
18         cin>>a>>b;
19         shu[a][b]=1;
20     }
21     for(ri i=1;i<=n;i++)
22     {
23         for(ri j=1;j<=n;j++)
24         {
25             if(!shu[i][j])
26             {
27                 f[i][j]=min(min(f[i][j-1],f[i-1][j]),f[i-1][j-1])+1;
28                 k=max(k,f[i][j]);
29             }
30         }
31     }
32     cout<<k<<'
';
33     return 0;
34 }
35 //