搜索给定尺寸的所有矩形的矩阵(选择座位块)
全,
我一直在考虑如何在一排座位中选择15张票。
编辑：问题是-如何找到所有给定尺寸的矩形(例如3x5 )的自由座位？
下面是我的表，查询选择4个连续的座位(或15个或其他什么)，这很好.
但我想要做的是选择15个座位，这些座位可以分成多排，即3x5，但我希望它们一起被阻塞。
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,
a.row, a.seat AS start_seat,
a.seat + (4 - 1) AS end_seat,
4 AS requested_seats,
a.id AS start_allocation_id
FROM seats a
LEFT JOIN seats b ON
a.event_id = b.event_id AND
a.performance = b.performance AND
a.block = b.block AND
a.row = b.row AND
a.seat < b.seat AND
b.seat < a.seat + 4 AND
b.status = 1
WHERE a.status = 1 AND
a.event_id = 1
GROUP BY a.seat
HAVING COUNT(b.seat) + 1 = 4
ORDER BY performance谢谢提前，需要更多的信息，请直接问！
回答 7
Stack Overflow用户
发布于 2011-09-08 19:07:51
这个问题在mysql之外用另一种语言更好地解决。换句话说，你有一个座位矩阵，其中一些是被占用的(灰色的)：
你想要找到所有给定尺寸的矩形，比如说3x5。通过两次传递O(n)线性时间算法(n为座位数)，您可以非常有效地完成这一任务：
( 1)在第一次通过时，从下到上按列进行，对于每个座位，表示在此之前可以使用的连续座位数：
重复，直到：
( 2)在第二遍中，按行走，查找至少5个大于或等于3:的连续数字
所以，最后，你得到：
这产生了解决方案:这些数字序列(绿色区域)是两个可能的矩形3x5的自由座位的顶部边缘。
该算法可以方便地进行改进，如得到面积最大的所有矩形。或者，它可以用来找出N个座位的任何连续区域(不仅仅是矩形)--在第二次传递时，只需查找至少可以归纳为N的连续数列。
Stack Overflow用户
发布于 2011-08-07 07:10:23
根据您的描述，这不是数据库问题，而是算法问题。我建议一个平铺模式，可能是四叉树，或者是填充空间曲线。也许MySQL中的空间索引也能帮助您解决问题。A si将2d平面细分为4块。
Stack Overflow用户
发布于 2015-05-24 00:12:54
我来这里是为了寻找Python解决方案。这是我的，它返回所有的位置：
import numpy
s = '''0 0 0 0 1 0 0 0 1 0 0
0 0 0 0 0 0 1 0 1 0 1
0 1 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0'''
area = 15
nrows = 6
ncols = 11
skip = 1
a = numpy.fromstring(s, dtype=int, sep=' ').reshape(nrows, ncols)
w = numpy.zeros(dtype=int, shape=a.shape)
h = numpy.zeros(dtype=int, shape=a.shape)
for r in range(nrows):
for c in range(ncols):
if a[r][c] == skip:
continue
if r == 0:
h[r][c] = 1
else:
h[r][c] = h[r-1][c]+1
if c == 0:
w[r][c] = 1
else:
w[r][c] = w[r][c-1]+1
minw = w[r][c]
for dh in range(h[r][c]):
minw = min(minw, w[r-dh][c])
if (dh+1)*minw == area:
print(
'area', area, 'row', r, 'col', c,
'height', dh+1, 'width', minw)输出：
area 15 row 4 col 8 height 3 width 5
area 15 row 5 col 10 height 3 width 5https://stackoverflow.com/questions/6945105
复制相似问题
腾讯云开发者
