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币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!