相关疑难解决方法(0)

给定NxN二进制矩阵(仅包含0或1),我们如何才能找到包含全0的最大矩形？

例:

      I
    0 0 0 0 1 0
    0 0 1 0 0 1
II->0 0 0 0 0 0
    1 0 0 0 0 0
    0 0 0 0 0 1 <--IV
    0 0 1 0 0 0
            IV 

对于上面的例子,它是一个6×6的二进制矩阵.在这种情况下,返回值将是单元格1:(2,1)和单元格2:(4,4).得到的子矩阵可以是正方形或矩形.返回值也可以是所有0的最大子矩阵的大小,在该示例中为3×4.

所有,

我一直试图找出如何在一个座位内选择15张票.

编辑:问题是 - 如何找到给定尺寸的所有矩形(例如3x5)的免费座位？

下面是我的表,查询选择4个连续席位(或15或其他),这是好的...

但我想做的是选择说15个座位,这些可以分成多行,即3 x 5,但我希望它们被封锁在一起,即

row 9 ..(some seats)..[5 seats]..(some seats)..
row 8 ..(some seats)..[5 seats]..(some seats)..
row 7 ..(some seats)..[5 seats]..(some seats)..

也就是说,他们将在彼此前面排成3排.row9座位10到25,row8座位10到25,row7座位10到25.

还可能需要考虑座椅块是否具有不同数量的座椅,即角块可以呈弧形以在后部具有比前部更多的座椅.

以ehnaceing SQL或某些算法或某些PHP代码的形式提供的任何指导.一周的大部分时间里,我一直在捣乱自己的大脑.

CREATE TABLE `seats` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `event_id` int(11) DEFAULT NULL,
  `performance` int(11) DEFAULT NULL,
  `block` int(11) DEFAULT NULL,
  `row` int(11) DEFAULT NULL,
  `seat` int(11) DEFAULT NULL,
  `status` int(10) DEFAULT 1,
  PRIMARY KEY (`id`)
) ENGINE=MyISAM AUTO_INCREMENT=11 DEFAULT CHARSET=utf8;

我的查询到了 - 它返回X席的块组合.

SELECT    a.event_id, a.performance, a.block, …