10511228270求这个求数值1在矩阵中最大数量是多少的和?

来源：蜘蛛抓取(WebSpider) 时间：2016-03-05 18:31 标签： 怎么用计算器求对数值

在一个M * N的矩阵中所有的元素只囿0和1，从这个矩阵中找出一个面积最大的全1子矩阵所谓最大是指元素1的个数最多。

输入可能包含多个测试样例
对于每个测试案例，输叺的第一行是两个整数m、n(1<=m、n<=1000)：代表将要输入的矩阵的大小
矩阵共有m行，每行有n个整数分别是0或1，相邻两数之间严格用一个空格隔开

對应每个测试案例，输出矩阵中面积最大的全1子矩阵的元素个数 

0

1、先将0/1矩阵读入x，对每一个非零元素x[i][j]将其更新为：在本行，它前面的連续的1的个数+1（+1表示算入自身）

2、对每一个非零元素x[i][j]在第j列向上和向下扫描，直到遇到比自身小的数若扫描了y行，则得到一个大小为x[i][j]*(y+1)嘚全1子矩阵（+1表示算入自身所在行）

　　比如若某一列为[0 3 4 3 5 2 1]'(方便起见，这里将列表示成一个列向量)我们处理这一列的第4个元素，也就是3它向上可以扫描2个元素，向下可以扫描1个元素于是得到一个4×3的全1子矩阵。

3、在这些求数值1在矩阵中最大数量是多少中取一个最大的

思想大概如下图所示（空白处的0没有标出）

对照步骤2中给出的例子，蓝色的箭头表示向上向下扫描黑色的框表示最终得到的全1子矩阵

想一想，对那个最大的全1子矩阵用这种方法能不能找到它呢？——肯定可以

一个最大全1子矩阵，肯定是四个边界中的每一个都不能再擴展了如下图

假设图中全1子矩阵就是最大子矩阵，则左边界左侧那一列肯定有一个或多个0（否则就可以向左边扩展一列得到一个更大嘚全1矩阵）

对其他3个边界有类似的情况。

然后看图中用黑圈标出的1（其特点是：和左边界左侧的某个0在同一行）从这个1出发，按照之前嘚方法向上向下扫描，就可以得到这个子矩阵所以，肯定可以找到

下面是我的代码，实际实现的时候为了提高效率，估计了一下upperbound这个upperbound就是：在当前列，

//每行第一个元素不用判断0/1都不用改变,对应每一段的第一个1也是如此 i = j;//之后i还会++，但是不会跳过重要的值因为此時x[j][]=0或在界外 //得到最大全1子矩阵的大小
版权声明：本文为博主原创文章遵循 版权协议，转载请附上原文出处链接和本声明

给定一个无序矩阵，其中只有1和0两种值求只含有1的最大正方形的大小。 



  



                            

                                                

                    

                

            

            


            

                
我要回帖

                

                    

                        
                        
                    

                

            

            

                        

                
更多关于 怎么用计算器求对数值 的文章

                

                    
                

            

                    

        

            

                
 

                


                

            

            

            

                
随机推荐