【修桥游戏】求算法帝给个思路

lee1892

手工做了一遍，有点意思。主要是锻炼逻辑的。比如角落为2，其一侧为1或2时，另一侧至少有一个连接。

贴图的这题最后会形成两段链，剩下俩没连接的岛有两种方式连，一种能把两段连接起来，另一种则不行。估计这才是比较啰嗦的地方。

比较方便的编程方式是用类和事件驱动，一旦新连接桥就触发事件，直到没有新的事件产生。检查未连接的岛以及形成的链的情况。

Moneky

lee1892 发表于 2013-12-16 23:53
手工做了一遍，有点意思。主要是锻炼逻辑的。比如角落为2，其一侧为1或2时，另一侧至少有一个连接。

贴图 ...

居然纯手工做出来了，思维和耐心不是一般的好啊{:soso_e179:}，我1L那个是看了答案的最外圈才做出来的。。。。刚刚装了虚拟机和Ubuntu，找到了这个游戏发个自定义游戏的设置截图看看对思维是否有帮助吧。（在应用商店中名字叫“网桥”，在菜单中叫“Birdges”）

yiyiyicz

一个简单的方法
因为你只要求岛与岛之间连通。除了不能交叉，路径（桥）没有其它限制
所以
1，所有在一条竖线上的岛，统统用一条竖线链接起来。也就是在这条竖线上的岛，从上到下顺序建岛--岛之间的桥
2，每条竖线上找一个岛与相邻竖线上的一个岛，建岛--岛之间的桥
这样，所有的岛之间都是连通的。只是有些岛之间路远点。但符合1楼的要求
编程也简单

yiyiyicz

如果还有限制性要求，那用神经网络、图等复杂的工具来解决是适宜的
如果仅仅是1楼的要求，还是怎么简单怎么来比较好

lee1892

Moneky 发表于 2013-12-16 22:48
先前学习了一些类的知识，所以先想到创建如下的类：

目前也只是想想而已，还不能动手，因为后面的算法 ...

楼主有啥进展不～

如果用类来写的话，我琢磨可以设置如下几个：
1、单个岛
2、岛集合
3、单个桥
4、桥集合
5、游戏

单个岛里有邻近岛索引集合，单个桥有连接的岛的信息和与其相交的桥的索引集合。
游戏里申明一个岛集合、一个桥集合。初始化时，桥集合生成全部可能的桥，做好干涉桥连接。

桥设置状态为建立，触发事件
桥设置状态为不采用，触发事件
岛去除邻近岛，触发事件

不过我觉得直接用自定义数据类型结合数组、集合之类的，用循环不断检查，代码量小不少，也容易调试。

几种做题逻辑里，估计最麻烦的是判断是否产生孤立链。

Moneky

lee1892 发表于 2013-12-17 19:42
楼主有啥进展不～

如果用类来写的话，我琢磨可以设置如下几个：

现在工作上的事情太多，没有时间和精力来完成，当然想法也不成熟。
把这个问题发上来是供诸位精力充沛的大神消遣用的。

我的话等后面有时间了再来思考与写代码，现在先观望你们了，惭愧。。。。

Moneky

lee1892 发表于 2013-12-17 19:42
楼主有啥进展不～

如果用类来写的话，我琢磨可以设置如下几个：

学了类的知识后，我觉得还是采用类代码会更加直观点。

“自定义数据类型结合数组、集合之类的，用循环不断检查”，代码会不会不好看懂啊。
采用事件触发，我想是不是像这样：任意两座桥和岛之间有这样的逻辑，岛A向正确的岛B建桥，但不是立即成功，而是向岛B申请，由岛B审查，岛B审查的过程就是，岛B向他的下个岛（C，D，E。。。。）申请搭桥，如果岛B发现自己可以可以正常搭桥的话，则批准岛A的建桥申请，桥搭建成功；否则，拒绝岛A的建桥申请，然后岛A再向另一个岛发出申请。

说的很绕口，写完后又有点像（回溯、递归）什么的，我不清楚专业名词，错误莫笑。。。。。但这些岛太多了，会不会出现“溢出堆栈”的错误

lee1892

孤立链的问题，可以在建桥过程中构造链的集合，两个链一旦联通就合并，同时监视链中剩余的未完成链接的岛。所以整个游戏由3个数据组成，岛、桥、链。
基本是个线性问题，和数独的难度差太多了，怪不得不流行，呵呵。


不过拿这个练习写类代码倒是不错的，尤其是练习事件驱动的方式，还有集合类。以岛为例，写一个单个岛的类代码很简单，但一堆数目不定的岛，同时要产生事件，就必须另外写个集合类，或者都放到一起那代码就没法看了。

建议你如果有时间就练练写类，否则直接几个过程就解决了。

另外，写代码前多找些不同的题做做，这种解题代码要想写好首先要把游戏玩好，呵呵～
你的想法已经岔了～

话说蛮合适做为一个开放式竞赛题的。

Moneky

lee1892 发表于 2013-12-17 23:15
孤立链的问题，可以在建桥过程中构造链的集合，两个链一旦联通就合并，同时监视链中剩余的未完成链接的岛。 ...

呵呵，我是只作爱好，所以可以悠着点

lee1892

1		3		3		2		2		2			2				2		2		2		1
	1				2		4		4			3		3		5		5		5		3		2
				2				1		3			2										1
1		1			1																	1		2
	2			6			6			7		4		5		7		4		4			3
3			1										1				1					2		2
	4			5			3			5		4		4		3			3		3		1
2																						4		3
	3				2			4		4			2		2			3			3
3			3				1				1					3				4		6		4
	2			2		3		7		5		5		3			1		2		1		2
2																5		2		3		2		2
	4		5		5			6		7		6		4			1		4		4		4
2																								3
	4		7		5		2			4		4		8		5		1					3
2				3				3					1								3			3
			2			1			5		6			7			3		4				3
	3			3				1					1											2
			1												2		6		6		5		3
2						1			4		4		2											2
	4			5				4		2		3		7			4			5			3
		1																	2			3		5
	2					1		4			2			4		1				3
1		2		4			2			2		2			2		3		3
	2		2		2				2		2			2		2		2		2		2		3

放个难的，备查，呵呵~