EMC笔试题(最后一道编程题)

14年前
题目是这样的: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 #  # # # #
# # #  # # # #
# # #  # # # #
# # #  # # # #
# # #  # # # #
两个球相邻是不能动的。中间一定要有至少一个的空格。
当碰撞过后,只有一个球在棋盘上为有解。否则无解。
每次选择任意一个球开始运动,碰撞完成后,可以选择任意剩下小球开始运动。
请写出一个程序,任意初始化棋盘上的小球,然后判断是否有解,有解打印出球移动步骤,否则输入无解。