EMC笔试题（最后一道编程题）

昨天去EMC面试，有个题没写出来，只写了个思路，想和大家讨论下
题目是这样的：7*8的一个棋盘，即有56个格子。格子上随机放上小球。小球只可以做水平或者垂直方向运动。
小球相互可以碰撞，碰撞的情况为：
如果两个小球相邻，比如Ball(1, 3)和Ball (1, 4)，这时远处的小球Ball(1, 1)移动过来撞到Ball(1, 3)，Ball(1, 1)应该停止在(1, 2)位置，同时Ball(1, 3)把碰撞传递给Ball(1, 4)后，Ball(1,3)仍然不动， Ball(1, 4)被撞开，以此类推。



Ball(1, 1) => Ball(1, 3), Ball(1, 4)

如果一个方向上没有其他的小球存在，那么不允许直接将小球沿着这个方向直接移出棋盘。

例如下图中，G表示小球，那么(2,2)位置上的小球只能向右或向下移动，因为(2, 2)位置的小球的上方和左方都没有小球，规则不允许把(2, 2)位置的小球沿上、左方移动从而直接移出棋盘。同理，(4, 2)位置的小球只允许向左移动。

＃＃＃ # # # #
＃G # G # # #
# # #  # # # #
# G #  # # # #
# # #  # # # #
# # #  # # # #
# # #  # # # #
# # #  # # # #
两个球相邻是不能动的。中间一定要有至少一个的空格。
当碰撞过后，只有一个球在棋盘上为有解。否则无解。
每次选择任意一个球开始运动，碰撞完成后，可以选择任意剩下小球开始运动。
请写出一个程序，任意初始化棋盘上的小球，然后判断是否有解，有解打印出球移动步骤，否则输入无解。

评论

10 楼 zhizhuodeyu 2010-12-01  

没有看懂题目。

为何没有两个小球碰撞情况。

此题可否如此理解，三个小球只要横坐标或纵坐标相同，此题误解。或是两个小球碰撞后横坐标或纵坐标相邻此题无解
其他情况均为有解。

9 楼 suntao19830709 2010-11-30  

正面做这个问题可以，但是比较麻烦。例如需要递归，每一步还需要记住当前棋盘小球的位置。而且由于递归的需要，可能要创建大量的这样的位置信息。

但是这个题目并没有限定死，任意初始化棋盘上的小球，然后判断是否有解，有解打印出球移动步骤，否则输入无解。
关键这个任意并不是要输出全部的。我们完全可以模拟一种“伪任意”，可以按照下面偷个巧。

按下面步骤：
1：一开始随机生成一个任意位置的小球
2：假想这个小球是x，是另一个随机的小球y撞过来的。
3：把第二步的y当成x，再新建一个随机的小球y，假想它撞了当前的x(第二步里的y)
4：重复若干次步骤3
5：把最终各个小球的位置当成初始位置，然后逆向打出上面的结果。

如果要无解的那种有点类似上面有人提到的，生成一个类似8皇后的即可。

这样其实比较容易。以前看到有的游戏不会创建无解的初始位置，相信通过这种方式比较容易实现。

8 楼 tomorrow009 2010-11-30  

疑惑：小球是只有从“远处”移动过来才可以碰撞么？
即： 假如最后剩下两个相邻小球， b1(1,2) , b2(2,2), 那么是否可以使用b1撞走b2,而b1位置不变，并认定为有解呢？

7 楼 guispor7 2010-11-30  

junlas 写道

LZ，题目我看不懂，有个疑惑：

不允许直接将小球沿着这个方向直接移出棋盘，碰撞过后，"有解"怎么就一个球在棋盘上呢？？其它球呢？不懂~~

就是有球撞才能动，球要是被别的球撞出去的。不能自己跑出棋盘。

6 楼 junlas 2010-11-30  

LZ，题目我看不懂，有个疑惑：

不允许直接将小球沿着这个方向直接移出棋盘，碰撞过后，"有解"怎么就一个球在棋盘上呢？？其它球呢？不懂~~

5 楼 guispor7 2010-11-30  

CnXiaowei 写道

我觉得是不是这个思路：
从任意一个小球开始，先找一个有其他小球的方向移动，移动到其他小球的时候，和那个小球合并，再继续找另一个小球的方向进行移动，以此类推，直到四个方向都没有任何小球的时候，回溯到上一步，继续上一步找其他方向的小球移动，直到棋盘上只剩下一个小球，为找到的解，或者回溯到了最开始并且没有任何可移动的方向，则这个小球的位置开始无解，继续下一个小球的位置继续找。
其实就是回溯算法

不是替代原球，是在这个球的前方停下。
您的思路和我当时写得一样的。就是状态太多，不知道用什么来存储老的状态。

4 楼 CnXiaowei 2010-11-30  

我觉得是不是这个思路：
从任意一个小球开始，先找一个有其他小球的方向移动，移动到其他小球的时候，和那个小球合并，再继续找另一个小球的方向进行移动，以此类推，直到四个方向都没有任何小球的时候，回溯到上一步，继续上一步找其他方向的小球移动，直到棋盘上只剩下一个小球，为找到的解，或者回溯到了最开始并且没有任何可移动的方向，则这个小球的位置开始无解，继续下一个小球的位置继续找。
其实就是回溯算法

3 楼 lyw985 2010-11-30  

regular 写道

变种八皇后问题。

显然不是八皇后问题的变种，拜托看清题目再回答

2 楼 EldonReturn 2010-11-29  

除了推演+剪枝，暂时没想到更好的办法

1 楼 regular 2010-11-29  

变种八皇后问题。