2 wangtong2800 wangtong2800 于 2016.03.01 16:22 提问

求高手解答,一个小算法

以前有人提过这么一个问题,一个01矩阵,求里面最大的由1组成的矩形。
现在我的问题是,一个01矩阵,行和列都可以互换(3行5行对调,4列6列对调等),求里面可以有多少个矩形,最大矩形多大
0100000001
1110000001
0101010101
0010101010
0101000100
上面写的数是个例子,矩阵可以很大

2个回答

ly601579033
ly601579033   2016.03.01 17:09

行列随意换,就是随意组合啊~~
假入行列为 x,y ; 有n个0,m个1

size = 0;

    if  n>=4   size = size + (n*(n-1)*(n-2)*(n-3))  * ( x-1)( y-1)   //4个点全0组成矩形个数
            ... ... ...      依次计算6个点,8个点,9个点

至于最大矩形:
L = (m>n?m:n)
Max = (L%2==0)?(L*L/4):((L/2)*(L/2+1))

wangtong2800
wangtong2800 不对,行或者列变化位置,不是单个元素互换,你0不一定可以组成对的图形,明白吗,你数数是没用的
2 年多之前 回复
ly601579033
ly601579033 回复wangtong2800:加入规定只进行一次变换(行或者列),那就不是统计了。随意进行行列变换(变换n次,n穷举),就是统计啊
2 年多之前 回复
wangtong2800
wangtong2800 我差点激动了,不过我不是这个意思啊,行互换是整行的换,列也是,你换完不一定是矩形明白吗?你这不成了统计0,1个数了嘛
2 年多之前 回复
xianfajushi
xianfajushi   2016.03.01 20:14

行数阶乘+列数阶乘个数量?

wangtong2800
wangtong2800 你这是全是一,数格子呢?再说也不是加法
2 年多之前 回复
wangtong2800
wangtong2800 穷举法是不可行的,你计算就知道了,稍微大一点的矩阵就得报废
2 年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
内存溢出小程序
一个小程序,有内存泄漏的问题,求高手解答。
坦克大战源代码
坦克大战源代码,还只有基本引擎,图片显示有问题,求高手解答
如何转换成NC文件
怎么将精雕5.21软件转换NC格式的G代码文件求高手解答。
算法:求第k小元素
学习算法时一个求第k小元素的小例子。内含代码和输入文件。很好用哦!
求一个集合子集的算法示例
求一个集合子集的算法示例, 用两种方法解,一种是基于回溯的递归求解,一种基于位域映射.
交通灯半成品求高手解答
交通灯的半成品交通灯的半成品交通灯的半成品交通灯的半成品交通灯的半成品交通灯的半成品交通灯的半成品交通灯的半成品交通灯的半成品交通灯的半成品
求平面点集最近点对的一个改进算法
求平面点集最近点对的一个改进算法,求平面点集最近点对的一个改进算法
一个网页邮件采集软件
一个网页邮件采集软件求高手破解
c# 个人计算器
个人做的一个计算器,新手请勿喷,求高手指导
转化为逆波兰表达式
C语言:设计一个算法,将一般算术表达式转化为逆波兰表达式,并求逆波兰表达式的值。数据结构实验