IT知识库 购物 网址 游戏 小说 歌词 快照 开发 股票 美女 新闻 笑话 | 汉字 软件 日历 阅读 下载 图书馆 编程 China
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
vbs/VBScript DOS/BAT hta htc python perl 游戏相关 VBA 远程脚本 ColdFusion ruby专题 autoit seraphzone PowerShell linux shell Lua Golang Erlang 其它教程 CSS/HTML/Xhtml html5 CSS XML/XSLT Dreamweaver教程 经验交流 开发者乐园 Android开发资料
站长资讯 .NET新手 ASP.NET C# WinForm Silverlight WCF CLR WPF XNA VisualStudio ASP.NET-MVC .NET控件开发 EntityFramework WinRT-Metro Java C++ PHP Delphi Python Ruby C语言 Erlang Go Swift Scala R语言 Verilog 其它语言 架构设计 面向对象 设计模式 领域驱动 Html-Css JavaScript jQuery HTML5 SharePoint GIS技术 SAP OracleERP DynamicsCRM K2 BPM 信息安全 企业信息 Android开发 iOS开发 WindowsPhone WindowsMobile 其他手机 敏捷开发 项目管理 软件工程 SQLServer Oracle MySQL NoSQL 其它数据库 Windows7 WindowsServer Linux
  IT知识库 -> C++ -> 面积最大的全1子矩阵 -> 正文阅读

[C++]面积最大的全1子矩阵

面积最大的全1子矩阵 题目描述:
在一个M * N的矩阵中,所有的元素只有0和1,从这个矩阵中找出一个面积最大的全1子矩阵,所谓最大是指元素1的个数最多。
输入:
输入可能包含多个测试样例。
对于每个测试案例,输入的第一行是两个整数m、n(1<=m、n<=1000):代表将要输入的矩阵的大小。
矩阵共有m行,每行有n个整数,分别是0或1,相邻两数之间严格用一个空格隔开。
输出:
对应每个测试案例,输出矩阵中面积最大的全1子矩阵的元素个数。
样例输入:

2 2
0 0
0 0
4 4
0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0

样例输出:0 4
解题思路:转载自http://www.cnblogs.com/fstang/archive/2013/05/19/3087746.html
方法是:
1、先将0/1矩阵读入x,对每一个非零元素x[i][j],将其更新为:在本行,它前面的连续的1的个数+1(+1表示算入自身)
  比如,若某一行为0 1 1 0 1 1 1,则更新为0 1 2 0 1 2 3
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、在这些数值中取一个最大的。
思想大概如下图所示(空白处的0没有标出)

对照步骤2中给出的例子,蓝色的箭头表示向上向下扫描,黑色的框表示最终得到的全1子矩阵
这样做为什么是对的?
想一想,对那个最大的全1子矩阵,用这种方法能不能找到它呢?——肯定可以。
一个最大全1子矩阵,肯定是四个边界中的每一个都不能再扩展了,如下图

假设图中全1子矩阵就是最大子矩阵,则左边界左侧那一列肯定有一个或多个0(否则就可以向左边扩展一列,得到一个更大的全1矩阵)
对其他3个边界有类似的情况。
然后看图中用黑圈标出的1(其特点是:和左边界左侧的某个0在同一行),从这个1出发,按照之前的方法,向上向下扫描,就可以得到这个子矩阵。所以,肯定可以找到。
下面是我的代码,实际实现的时候,为了提高效率,估计了一下upperbound,这个upperbound就是:在当前列,
包含x[i][col]的连续的非零序列的和,比如对某列[0 3 4 3 5 2 1]',后面6个的upperbound都是
3 + 4 + 3 + 5 + 2 + 1 = 18,对于0元素,不需要upperbound


 1 #include<iostream>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     int n,m;
 7     while(cin>>n>>m){
 8         int **array=new int*[n];
 9         int **upperbound=new int*[n];
10         for(int i=0;i<n;i++){
11             array[i]=new int[m];
12             upperbound[i]=new int[m];
13             for(int j=0;j<m;j++){
14                 cin>>array[i][j];
15                 upperbound[i][j]=0;
16             }
17         }
18         //prepare:
19         for(int i=0;i<n;i++){
20             for(int j=1;j<m;j++){
21                 if(array[i][j]==1&&array[i][j-1]!=0)array[i][j]=array[i][j-1]+1;
22             }
23         }
24         //计算upperbound
25         for(int j=0;j<m;j++){
26             for(int i=0;i<n;i++){
27                 if(array[i][j]==0)continue;
28                 else{
29                     int sum=0,temp=i;
30                     while(temp<n&&array[temp][j]>0){
31                         sum+=array[temp][j];
32                         temp++;
33                     }
34                     for(int k=i;k<temp;k++){
35                         upperbound[k][j]=sum;
36                     }
37                     i=temp;
38                 }
39             }    
40         }
41 
42         int maxarea=0;
43         for(int i=0;i<n;i++){
44             for(int j=0;j<m;j++){
45                 if(array[i][j]!=0&&maxarea<upperbound[i][j]){
46                     int cnt=1,val=array[i][j];
47                     for(int row=i-1;row>0;row--){
48                         if(array[row][j]>=val)cnt++;
49                         else
50                             break;//这里一定要break
51                     }
52                     for(int row=i+1;row<n;row++){
53                         if(array[row][j]>=val)cnt++;
54                         else
55                             break;//这里一定要break
56                     }
57                     if(cnt*val>maxarea)maxarea=cnt*val;
58                 }
59             }
60         }
61         cout<<maxarea;
62     }
63     return 0;
64     
65 }

View Code
上一篇文章      下一篇文章      查看所有文章
加:2015-05-12 19:30:03  更:2017-05-15 12:25:43 
 
  C++ 最新文章
关于poin与references
019:别叫,这个大整数已经很简化了!
c++智能指针详解
BZOJ1269: [AHOI2006]文本编辑器editor
洛谷P3835 【模板】可持久化平衡树
洛谷P2925 [USACO08DEC]干草出售Hay For Sa
算24点的算法,有输出
Codeforces Round #234A
[C++]C++类基本语法
[BZOJ]3737 [Pa2013]Euler
技术频道: 站长资讯 .NET新手区 ASP.NET C# WinForm Silverlight WCF CLR WPF XNA Visual Studio ASP.NET MVC .NET控件开发 Entity Framework WinRT/Metro Java C++ PHP Delphi Python Ruby C语言 Erlang Go Swift Scala R语言 Verilog 其它语言 架构设计 面向对象 设计模式 领域驱动设计 Html/Css JavaScript jQuery HTML5 SharePoint GIS技术 SAP Oracle ERP Dynamics CRM K2 BPM 信息安全 企业信息化其他 Android开发 iOS开发 Windows Phone Windows Mobile 其他手机开发 敏捷开发 项目与团队管理 软件工程其他 SQL Server Oracle MySQL NoSQL 其它数据库 Windows 7 Windows Server Linux
脚本语言: vbs/VBScript DOS/BAT hta htc python perl 游戏相关 VBA 远程脚本 ColdFusion ruby专题 autoit seraphzone PowerShell linux shell Lua Golang Erlang 其它教程
网站开发: CSS/HTML/Xhtml html5 CSS XML/XSLT Dreamweaver教程 经验交流 开发者乐园 Android开发资料
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 新闻资讯 小游戏 Chinese Culture 股票 三丰软件 开发 中国文化 网文精选 阅读网 看图 日历 万年历 2018年10日历
2018-10-24 3:20:25
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT知识库