洛谷 P4147 玉蟾宫 & P1169 [ZJOI2007]棋盘制作(求最大子矩阵)

题目： P4147 玉蟾宫： https://www.luogu.org/problemnew/show/P4147

　　　 P1169 [ZJOI2007]棋盘制作： https://www.luogu.org/problemnew/show/P1169

题目本质为求解矩阵中的最大子矩阵。

方法为：悬线法(具体参考： https://blog.csdn.net/Clove_unique/article/details/50512624 等相关文章)

建议手画一遍帮助理解。

P4147 玉蟾宫的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,end;
 8 bool a[1005][1005];
 9 ll L[1005][1005],R[1005][1005],H[1005][1005];
10 ll l[1005][1005],r[1005][1005];
11 char s;
12 
13 signed main()
14 {
15     ios::sync_with_stdio(0),cin.tie(0);
16     cin>>n>>m;
17     for(ri i=1;i<=n;i++)
18     {
19         for(ri j=1;j<=m;j++)
20         {
21             cin>>s;
22             if(s=='F')
23             {
24                 a[i][j]=1;
25             }
26         }
27     }
28     for(ri i=0;i<=n;i++)
29     {
30         ri t=0;
31         for(ri j=1;j<=m;j++)
32         {
33             if(a[i][j]) l[i][j]=t;
34             else L[i][j]=0,t=j;
35         }
36         t=m+1;
37         for(ri j=m;j>=1;j--)
38         {
39             if(a[i][j]) r[i][j]=t;
40             else R[i][j]=m+1,t=j;
41         }
42     }
43     for(ri i=1;i<=n;i++)
44     {
45         for(ri j=1;j<=m;j++)
46         {
47             if(a[i][j])
48             {
49                 H[i][j]=H[i-1][j]+1;
50                 L[i][j]=max(L[i-1][j],l[i][j]+1);
51                 R[i][j]=min(R[i-1][j],r[i][j]-1);
52                 end=max(end,(R[i][j]-L[i][j]+1)*H[i][j]);
53             }
54         }
55     }
56     cout<<end*3<<'
';
57     return 0;
58 }
59 //

注意事项：

　　28行最外层循环一定从0开始，因为处理第1行要用到第0行的数据。

　　34,40行一定要将L和R的值赋在两边，原因手动模拟一遍即可知。

　　50,51行调用l与r一定要将l+1，r-1。

另外：

　　在 P1169 [ZJOI2007]棋盘制作中：

　　　　首先是对于图上所有的棋盘一定属于以下两种类型：

　　　　　　1.黑格行列奇偶性相同，白格不同。

　　　　　　2.白格行列奇偶性相同，黑格不同。

　　　　那么在输入的时候属于第一种情况的赋1，属于第二种情况的赋0。

　　　　统计最大的1或0矩形和正方形就可以啦。