s******o 发帖数: 328 | 1 收拾一块黑棋或一块白棋算一次.如何用最少的次数收拾好棋子?
假设棋盘上无死子.注意收拾一次之后,多块棋可能变成一块棋. |
h*****0 发帖数: 4889 | 2 数学化一下:
每一块棋是一个点,相邻的棋之间有边连通。显然黑点只和白点连通。每次
收拾相当于抽掉一下点,将其相邻点全部合并为一点。
似乎不是太简单。
【在 s******o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 收拾一块黑棋或一块白棋算一次.如何用最少的次数收拾好棋子? : 假设棋盘上无死子.注意收拾一次之后,多块棋可能变成一块棋.
|
h**r 发帖数: 614 | 3 没看懂, 请定义收拾先.
【在 s******o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 收拾一块黑棋或一块白棋算一次.如何用最少的次数收拾好棋子? : 假设棋盘上无死子.注意收拾一次之后,多块棋可能变成一块棋.
|
h*****0 发帖数: 4889 | 4 直接解答我的数学模型吧
【在 h**r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 没看懂, 请定义收拾先.
|
h**r 发帖数: 614 | 5 先计算一下每快子有几个邻点, 先抽邻点最多的, 循环?
tie breaker 还没想好.
【在 h*****0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 数学化一下: : 每一块棋是一个点,相邻的棋之间有边连通。显然黑点只和白点连通。每次 : 收拾相当于抽掉一下点,将其相邻点全部合并为一点。 : 似乎不是太简单。
|
h*****0 发帖数: 4889 | 6 不对,应该是找到一个点,使这个点到其它任何点的最大长度最小,然后
一直收拾这个点(以及合并出来点)即可。
【在 h**r 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 先计算一下每快子有几个邻点, 先抽邻点最多的, 循环? : tie breaker 还没想好.
|
h*****0 发帖数: 4889 | 7 用围棋直接来说就是:
每一块棋都可以通过若干相邻棋到达任何另一块棋。通过的最小相邻棋数(包括最
后的一块棋)我们称为两块棋间的距离。找到一块棋,使其跟其它所有棋的距离
最大值最小。
【在 h*****0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 不对,应该是找到一个点,使这个点到其它任何点的最大长度最小,然后 : 一直收拾这个点(以及合并出来点)即可。
|
h**r 发帖数: 614 | 8 恩.
【在 h*****0 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 用围棋直接来说就是: : 每一块棋都可以通过若干相邻棋到达任何另一块棋。通过的最小相邻棋数(包括最 : 后的一块棋)我们称为两块棋间的距离。找到一块棋,使其跟其它所有棋的距离 : 最大值最小。
|