笔试被考倒的:矩形分割问题,谁能解答?(200分)

S

selonboy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-10-11

• #1

有一44*36矩阵,小单元格16*16
内部白色区域为随机填充的小单元格

现需要将白色区域分割成"最少矩形区"(凡相邻的白色单元格可以联合成一个大矩形),请写出算法.
详细请参考下面的图片:

http://www.selonsoft.com/rect.gif

想了半天愣是没想出来,结果可想而知.
现把此题张贴出来,求高人解答,不胜感激!
分少可以再加!

 

爱

爱不到要偷

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-10-11

• #2

解决问题部份能不能在说明一下

 

S

selonboy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-10-11

• #3

TO:爱不到要偷
解决问题部分在图片链接中有,白色区域因为是随机生成的,所以形状/大小也是不固定的,因此才求函数算法.
虽然形状不固定,但都是由16*16的小单元格(小矩形)组成的,所以可以把白色区域以横向或纵向的分割方式对这些白色的"小单元格"进行重组成一个较大的矩形区,但不能改变它们的位置.

问题已经很明确了:像分割板材一样,能分割成3个区域的就不要分成4个或更多,但是要求必须把这些白色区域分完.这样最后才可得出分割后的矩形区数量及分割后各矩形区的座标值(左上角顶点X,Y,右下角顶点X,Y)

 

爱

爱不到要偷

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-10-11

• #4

QQ75523263

 

Z

zbr

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-10-11

• #5

这个笔试题有意思 。 解答中····

 

W

wxy_xiaoyan

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-10-11

• #6

我觉得:
1. 44*36这个好象没有意义(对算法来说)
2.1 要解决这个问题，最好要找出一个另意相邻的白色小单元格（边相邻）的最少矩形区de函数
2.2 再找出每个边相邻的区域(10*12内)

 

R

runfan

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-10-11

• #7

有个问题，是必需全部分割完，还是可以留下些不管。
还有，分割后必需全部大小一样吗？

 

S

selonboy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-10-11

• #8

TO：wxy_xiaoyan
44*36对于算法的确是没有意义的;

TO:runfan
问题已经很明确了:像分割板材一样,能分割成3个区域的就不要分成4个或更多,但是要求必须把这些白色区域分完.这样最后才可得出分割后的矩形区数量及分割后各矩形区的座标值(左上角顶点X,Y,右下角顶点X,Y) 。

分割后大小并不需要一样。

[]

 

网

网中戏

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-10-11

• #9

顶

 

D

duhai_lee

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-10-11

• #10

试试a*算法吧。 这也算搜索的。

 

S

selonboy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-10-11

• #11

TO:duhai_lee
a*算法？能否贴点料上来，我没有搜到啊

 

Z

zfox

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-10-12

• #12

我觉得应该先进行一次全局扫描数组a[44,36]（假设白格的值是1，黑格的值是0），然后将数组中值为1的进行分类，也就是分区（横坐标相减+纵坐标相减=1的分在同一个区），再在个区中查找最少矩形，这个是我的想法，没试过，供参考参考：）

 

X

xulxqqqq

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-10-12

• #13

楼上的表达式不对吧？
(2,2) (4,1) 也分在一个区吗？
难道指的是取绝对值？

 

S

selonboy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-10-12

• #14

如何获取到白色填充区很容易,现在难的就是如何根据已知填充区(且每一次生成的不固定)这个动态数组划分出组成该区域的最小矩形数.

 

S

socid

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-10-12

• #15

直接在整个矩阵里搜也好，还是先搜出小单元也好都不是关键（无非计算次数的问题）
关键是白色区域分割的方法不唯一，如何分割才是关键

 

Z

zfox

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-10-12

• #16

在 既定 区域里分出的最小矩形数是不是可以理解为这样：分出的矩形尽可能的大？如果这样的话，可以这么考虑，取出该区域里坐标值最小和最大的两个，然后以这两个点为矩形的对角点，再判断里面是否全包含；如果不是，取次大的，依次循环

 

X

xing212

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-10-12

• #17

关注
相信这公司招不到人了

 

S

selonboy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-10-12

• #18

TO:zfox
"在 既定 区域里分出的最小矩形数是不是可以理解为这样：分出的矩形尽可能的大？"

这样理解是正确的.让分出的矩形尽可能大,实在分不上的就单独作为一个区,前提是必须分完所有的白色区域,而且划分次数最小(重新拼组生成的新矩形数量最少).

 

I

iamy

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-10-13

• #19

看看图论
哈哈
不过不确定能够解决
这应该来是个类似找最短路径的问题
用便历是肯定能够解决的
想好了思路先

 

Z

zfox

Unregistered / Unconfirmed

GUEST, unregistred user!

• 2006-10-13

• #20

楼主，在 既定区域 里分出一个最大的矩形后，余下的空间再寻找一个最大矩形，直到该区域里所有的单元格都分完为止（取坐标最小可以是 横坐标+纵坐标=最小，最大可以是|横坐标相减|+|纵坐标相减|=最大，这样所有坐标取完为止，做个遍历，我想应该可以的，就是麻烦点）

呵呵，我是想不出其他的办法哦，图论里最短路径好象跟这个问题还是有点差别的。