LA3029最大子矩阵-白红宇

LA3029最大子矩阵

阅读量：4646 次

发布时间：2019-06-09

本文共 1566 字，大约阅读时间需要 5 分钟。

LA3029最大子矩阵

【题目描述】：给定m*n的矩阵，其中一些格子是空格F，其他是墙R。找出一个全部由空地组成的面积最大的子矩阵，输出面积。

【算法分析】：

【决策方案】：所有的子矩阵，C(n,2)*C( m,2)种，加上确认空地，大约N^6的复杂度

【限制条件】：所有的方块都是空地

【最优评判准则】：面积最大

【思路分析】：

朴素算法的复杂度是N^6,肯定不能接受，所以我们看是否记忆化扫描一些变量。一个矩阵面积的关键量是长h和宽d。参考《指南》上的思路，分别用数组表示每一个矩阵的h和d，但问题又来了，矩阵本身都有n^4种，不可能存储下来。所以我们可以换一种方式。用[I][J]代表以这一点为中心，假设这一点包含在一个空着的矩形中，那么能取到的面积是多少？为了让递递推变量更少，我们只统计up[i][j]这点向上的空格数，left[i][j].向左的最大延伸（记住，我们需要形成矩形，所以更坏的情况是向右逼近），同理，right[i][j]是右边的。

因为我们上从上到下，从两边逼近，所以：

lefts[i][j]=max(lefts[i-1][j],lo+1);

Lo是从左到有的标记量，if (map[i][j]=='F') lo=j；

Right同理，详见代码。

【难点】：思路本身（数学建模的过程）、写递推时要考虑到所有情况

【完整代码】：

1 #include
         
           2 #include
          
            3 #include
           
             4 #include
            
              5 #include
             
               6 #include
              
                7 #include
               
                 8 #include
                
                  9 #include
                 
                  10 //#include
                  11 #define MAXN 1000+512 #define MAXM 400000+513 #define oo 1e914 #define eps 0.00115 #define PI acos(-1.0)//这个精确度高一些16 #define REP1(i,n) for(int i=0;i<=(n);i++)17 #define REP2(i,n) for(int i=1;i<=(n);i++)18 #define DREP2(i,n) for(int i=(n);i>=1;i--)19 #define LL long long20 using namespace std;21 22 char map[MAXN][MAXN];23 int up[MAXN][MAXN];24 int rights[MAXN][MAXN];25 int lefts[MAXN][MAXN];26 27 int cas,n,m;28 29 int main()30 {31 cin>>cas;32 for(;cas;cas--)33 {34 cin>>n>>m;35 REP2(i,n) REP2(j,m) {cin>>map[i][j];if (map[i][j]=='\n' || map[i][j]==' ') cin>>map[i][j];}36 // REP2(i,n) {REP2(j,m) cout<
                   
                    <<" ";cout<

【关键词】：数学，递推扫描

转载于:https://www.cnblogs.com/little-w/p/3521157.html

你可能感兴趣的文章