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

评论

30 楼 prettyinsight 2011-02-16  

<p>小弟用swing写了个演示程序，可以用鼠标拖动小球来撞击。如下是截图，代码在附件中。大家可以玩玩哈</p>
<p><br><img src="http://dl.iteye.com/upload/attachment/419422/9cbc644d-f8d8-30e5-b9a1-6929be0886ac.png" alt=""></p>

29 楼 prettyinsight 2011-02-14  

<p>我提供个A*算法的思路。  </p>
<p>胡乱写了些代码在附件中</p>
<p> </p>

28 楼 regular 2010-12-17  

object Main {
    type Matrix = List[List[Int]]

    def main(args : Array[String]) : Unit = {
        val matrix = List(
                List(0, 0, 0, 0, 0), 
                List(1, 0, 0, 0, 1), 
                List(0, 1, 0, 0, 0), 
                List(0, 0, 0, 1, 0), 
                List(0, 0, 0, 0, 0))
        analyze(matrix, 4) match {
            case Some(x) => println(x)
            case None =>
        }
    }

    def matrixToString(matrix: Matrix) : String = {
        val f = (l : List[Int]) => ("" /: l)(_ + " " + _).substring(1)
        ("" /: matrix)(_ + f(_) + "\n")
    }

    def analyze(matrix : Matrix, count: Int): Option[String] = {
        if (count == 1) {
            return Some(matrixToString(matrix))
        }
        val top = Array.make(matrix(0).length, -1)
        for (rowIdx <- 0 until matrix.length) {
            val row = matrix(rowIdx)
            var left = -1
            for (colIdx <- 0 until row.length) {
                val point = row(colIdx)
                if (point == 1) {
                    if (left != -1 && colIdx - left > 1) {
                         analyze(click(matrix, rowIdx, colIdx, Direction.West), count - 1) match {
                             case Some(x) => return Some(matrixToString(matrix)+ colIdx + "," + rowIdx + " <\n" + x)
                             case None =>
                         }
                        analyze(click(matrix, rowIdx, left, Direction.East), count - 1) match {
                             case Some(x) => return Some(matrixToString(matrix) + left + "," + rowIdx + " >\n" + x)
                             case None =>
                         }
                    }
                    if (top(colIdx) != -1 && rowIdx - top(colIdx) > 1) {
                        analyze(click(matrix, rowIdx, colIdx, Direction.North), count - 1) match {
                             case Some(x) => return Some(matrixToString(matrix) + colIdx + "," + rowIdx + " ^\n" + x)
                             case None =>
                         }
                        analyze(click(matrix, top(colIdx), colIdx, Direction.South), count - 1) match {
                             case Some(x) => return Some(matrixToString(matrix) + colIdx + "," + top(colIdx) + " v\n" + x)
                             case None =>
                         }
                    }
                    left = colIdx
                    top(colIdx) = rowIdx
                }
            }
        }
        return None
    }
    
    def click(matrix : Matrix, rowIdx : Int, colIdx : Int, dir : Direction.Value) : Matrix = {
        dir match {
            case Direction.West =>
                val row = matrix(rowIdx).toArray
                row(colIdx) = 0
                goLeft(row, colIdx)
                val (top, bottom) = matrix.splitAt(rowIdx)
                top ::: row.toList :: bottom.tail
            case Direction.East =>
                val row = matrix(rowIdx).toArray
                row(colIdx) = 0
                goRight(row, colIdx)
                val (top, bottom) = matrix.splitAt(rowIdx)
                top ::: row.toList :: bottom.tail
            case Direction.North =>
                val col = Array.make(matrix.length, -1)
                for (row <- 0 until col.length) {
                    col(row) = matrix(row)(colIdx)
                }
                col(rowIdx) = 0
                goLeft(col, rowIdx)
                repCol(matrix, col, colIdx)
            case Direction.South =>
                val col = Array.make(matrix.length, -1)
                for (row <- 0 until col.length) {
                    col(row) = matrix(row)(colIdx)
                }
                col(rowIdx) = 0
                goRight(col, rowIdx)
                repCol(matrix, col, colIdx)
        }
    }
    def goLeft(row : Array[Int], idx : Int) {
        for (col <- idx - 1 to (0, -1)) {
            if (row(col) == 1) {
                row(col) = 0
                row(col + 1) = 1
            }
        }
    }
    def goRight(row : Array[Int], idx : Int) {
        for (col <- idx + 1 until row.length) {
            if (row(col) == 1) {
                row(col) = 0
                row(col - 1) = 1
            }
        }
    }
    def repCol(matrix : Matrix, col : Array[Int], colIdx : Int): Matrix = {
        for (pair <- matrix zip col) yield {
            val (row, point) = pair
            val (left, right) = row.splitAt(colIdx)
            left ::: point :: right.tail
        }
    }
}

object Direction extends Enumeration {
    val North, East, South, West = Value
}

27 楼 喜羊羊与灰太狼 2010-12-11  

我原来的v3手机里有这个游戏，^_^

26 楼 cqabl 2010-12-10  

玩过一个手机游戏,疯狂毛球对对碰,游戏规则跟楼主说的一模一样.

25 楼 superobin 2010-12-08  

楼上的答案好像很标准，呵呵~
我来个另类的吧，性能应该相对好一点，尤其是没有每次都克隆一堆数组。用的位操作，理论上说应该支持递归深度63以内的计算~

import java.util.ArrayList;
import java.util.List;

public class PongBall {
	private int[] size;
	List<int[]> steps = new ArrayList<int[]>();
	private long[][] pad;

	public PongBall(int sizeX, int sizeY) {
		this.size = new int[] { sizeX, sizeY };
		this.pad = new long[size[0]][size[1]];
	}

	public static void main(String[] args) {
		//*随机结果
		String[] direction = { "右", "下", "左", "上" };
		PongBall p = new PongBall(7,8);
		p.randomBall(5);
		String startStatus = "起始状态:\r\n" + p;
		System.out.println(startStatus);
		if (p.moveBall()) {
			for (int[] ary : p.steps) {
				System.out.println("在数组坐标：(" + ary[0] + "," + ary[1] + ")处碰撞,方向：" + direction[ary[2]]);
			}
			System.out.println("最终结果：\r\n" + p);
		} else {
			System.out.println("无解！");
		}
		//*/
		/*必然出现一个结果
		String[] direction = { "右", "下", "左", "上" };
		PongBall p;
		boolean result;
		String startStatus ;
		do {
			p = new PongBall(7,8);
			p.randomBall(5);
			startStatus = "起始状态:\r\n" + p;
		} while(!(result=p.moveBall()));
		System.out.println(startStatus);
		if (result) {
			for (int[] ary : p.steps) {
				System.out.println("在数组坐标：(" + ary[0] + "," + ary[1] + ")处碰撞,方向：" + direction[ary[2]]);
			}
			System.out.println("最终结果：\r\n" + p);
		} else {
			System.out.println("无解！");
		}
		//*/
	}
	public boolean moveBall() {
		upBit();
		boolean result = _moveBall();
		if(!result) {
			downBit();
		}
		return result;
	}
	private boolean _moveBall() {
		int cnt = 0;
		for (int i = 0; i < size[0]; i++) {
			for (int j = 0; j < size[1]; j++) {
				if ((pad[i][j] & 1) == 1) {
					cnt++;
					for (int d = 0; d < 4; d++) {
						int x = i, y = j, hitCount = 0;
						for (int step = 0; step >= 0; step++) {
							int dx = (2 - d) * (d & 1), dy = (1 - d) * ((d + 1) & 1);
							x += dx;
							y += dy;
							if (x >= size[0] || x < 0 || y >= size[1] || y < 0) {// 当有球到边界时
								if (hitCount > 0) {// 有过碰撞
									pad[x - dx][y - dy] &= -2;// 最后一位清零
									return moveBall();
								} else {// 没有碰撞
									recover();
									break;
								}
							}
							if ((pad[x][y] & 1) == 0) {// 下一位为空
								pad[x - dx][y - dy] &= -2;
								pad[x][y] |= 1;
							} else {// ==1
								if (step == 0) {// 两球紧挨
									recover();
									break;
								} else {// 碰撞
									steps.add(new int[] { x - dx, y - dy, d });
									hitCount++;
								}
							}
						}
					}
				}
			}
		}
		return cnt == 1;
	}

	private void upBit() {
		for (int i = 0; i < size[0]; i++) {
			for (int j = 0; j < size[1]; j++) {
				pad[i][j] <<= 1;
				pad[i][j] |= ((pad[i][j] >>> 1) & 1);
			}
		}
	}

	private void downBit() {
		for (int i = 0; i < size[0]; i++) {
			for (int j = 0; j < size[1]; j++) {
				pad[i][j] >>>= 1;
			}
		}
	}

	private void recover() {
		for (int i = 0; i < size[0]; i++) {
			for (int j = 0; j < size[1]; j++) {
				pad[i][j] &= Integer.MAX_VALUE - 1;
				pad[i][j] |= (pad[i][j] >>> 1) & 1;
			}
		}
	}

	public void randomBall(int ballCount) {
		if (size[0] * size[1] < ballCount) {
			throw new RuntimeException("Too many balls!");
		}
		int currentCount = 0;
		while (currentCount < ballCount) {
			int padX = (int) (Math.random() * size[0]);
			int padY = (int) (Math.random() * size[1]);
			if (pad[padX][padY] == 0) {
				currentCount++;
				pad[padX][padY] = 3;
			}
		}
	}

	public String toString() {
		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < pad.length; i++) {
			for (int j = 0; j < pad[i].length; j++) {
				sb.append((pad[i][j] & 1)==1?"O":"X").append(" ");
			}
			sb.append("\r\n");
		}
		return sb.toString();
	}
}

匆匆写的，没咋写注释而且很多判断应该还可以归并。。大致写个意思吧。。呵呵，勿喷勿喷。。。另外就现在的数据来说无解的情况比较多。。呵呵。。(O是球，X是空地)

24 楼 passionke 2010-12-07  

觉得这个题目很绕，不非常仔细看不知道在说什么

23 楼 newvirus 2010-12-07  

逆向推理 不错

22 楼 guispor7 2010-12-06  

yunzhiyifeng 写道

用上下左右的走递归写了个，求批。

import java.util.Random;

public class Main {
	private StringBuilder solution = new StringBuilder();

	public static void main(String[] args) {
		Main main = new Main();
		// main.doHit(main.generateTable(5, 5, 4));
		boolean[][] table = new boolean[5][5];
		table[0][0] = true;
		table[2][0] = true;
		table[3][0] = true;
		table[2][4] = true;
		table[3][0] = true;
		table[0][3] = true;
		System.out.println("table is: \n" + main.getTableString(table));
		main.doHit(table);
		if (main.solution.length() == 0) {
			System.out.println("There is not any solution");
		} else {
			main.solution.insert(0, "There is a solution.\n");
			System.out.println(main.solution.toString());
		}
	}

	public boolean[][] generateTable(int rowSize, int colSize, int nums) {
		boolean[][] table = new boolean[rowSize][colSize];
		Random random = new Random();
		while (nums != 0) {
			int x = random.nextInt(rowSize);
			int y = random.nextInt(colSize);
			if (table[x][y] == true) {
				continue;
			} else {
				table[x][y] = true;
				nums--;
			}
		}
		System.out.println("New generate table is: \n");
		System.out.println(getTableString(table));
		return table;
	}

	public boolean doHit(boolean[][] table) {
		for (int i = 0; i < table.length; i++) {
			for (int j = 0; j < table[i].length; j++) {
				if (table[i][j]) {
					if (goUp(table, i, j)) {
						return true;
					}
					if (goDown(table, i, j)) {
						return true;
					}
					if (goLeft(table, i, j)) {
						return true;
					}
					if (goRight(table, i, j)) {
						return true;
					}
				}
			}
		}
		return false;
	}

	private boolean goUp(boolean[][] table, int i, int j) {
		table = getNewCopy(table);
		boolean didHit = false;
		StringBuilder sb = new StringBuilder();
		sb.append("the ball at (").append(i).append(",").append(j).append(
				") hit the ball by up going.");
		if (i - 2 >= 0 && !table[i - 1][j]) {
			for (int k = i - 2; k >= 0; k--) {
				if (table[k][j]) {
					didHit = true;
					table[i][j] = false;
					table[k + 1][j] = true;
					table[k][j] = false;
					i = k;
				}
			}
		}
		sb.append(" After hit, the new table is:\n").append(
				getTableString(table));
		boolean result = checkAndDo(table, didHit);
		if (result) {
			solution.insert(0, sb.toString());
		}
		return result;
	}

	private boolean goDown(boolean[][] table, int i, int j) {
		table = getNewCopy(table);
		boolean didHit = false;
		StringBuilder sb = new StringBuilder();
		sb.append("the ball at (").append(i).append(",").append(j).append(
				") hit the ball by down going.");
		if (i + 2 < table.length && !table[i + 1][j]) {
			for (int k = i + 2; k < table.length; k++) {
				if (table[k][j]) {
					didHit = true;
					table[i][j] = false;
					table[k - 1][j] = true;
					table[k][j] = false;
					i = k;
				}
			}
		}
		sb.append(" After hit, the new table is:\n").append(
				getTableString(table));
		boolean result = checkAndDo(table, didHit);
		if (result) {
			solution.insert(0, sb.toString());
		}
		return result;
	}

	private boolean goLeft(boolean[][] table, int i, int j) {
		table = getNewCopy(table);
		boolean didHit = false;
		StringBuilder sb = new StringBuilder();
		sb.append("the ball at (").append(i).append(",").append(j).append(
				") hit the ball by left going.");
		if (j - 2 >= 0 && !table[i][j - 1]) {
			for (int k = j - 2; k >= 0; k--) {
				if (table[i][k]) {
					didHit = true;
					table[i][j] = false;
					table[i][k + 1] = true;
					table[i][k] = false;
					j = k;
				}
			}
		}
		sb.append(" After hit, the new table is:\n").append(
				getTableString(table));
		boolean result = checkAndDo(table, didHit);
		if (result) {
			solution.insert(0, sb.toString());
		}
		return result;
	}

	private boolean goRight(boolean[][] table, int i, int j) {
		table = getNewCopy(table);
		boolean didHit = false;
		StringBuilder sb = new StringBuilder();
		sb.append("the ball at (").append(i).append(",").append(j).append(
				") hit the ball by right going.");
		if (j + 2 < table[0].length && !table[i][j + 1]) {
			for (int k = j + 2; k < table[i].length; k++) {
				if (table[i][k]) {
					didHit = true;
					table[i][j] = false;
					table[i][k - 1] = true;
					table[i][k] = false;
					j = k;
				}
			}
		}
		sb.append(" After hit, the new table is:\n").append(
				getTableString(table));
		boolean result = checkAndDo(table, didHit);
		if (result) {
			solution.insert(0, sb.toString());
		}
		return result;
	}

	private boolean checkAndDo(boolean[][] table, boolean didHit) {
		if (isEnd(table)) {
			return true;
		} else {
			if (didHit) {
				return doHit(table);
			} else {
				return false;
			}
		}
	}

	private boolean[][] getNewCopy(boolean[][] table) {
		boolean[][] copy = table.clone();
		for (int i = 0; i < copy.length; i++) {
			copy[i] = table[i].clone();
		}
		return copy;
	}

	private boolean isEnd(boolean[][] table) {
		boolean haveOne = false;
		for (int i = 0; i < table.length; i++) {
			for (int j = 0; j < table[i].length; j++) {
				if (table[i][j] && !haveOne) {
					haveOne = true;
				} else if (table[i][j] && haveOne) {
					return false;
				}
			}
		}
		return true;
	}

	private String getTableString(boolean[][] table) {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < table.length; i++) {
			for (int j = 0; j < table[i].length; j++) {
				if (j != 0) {
					sb.append(" , ");
				}
				if (table[i][j]) {
					sb.append("O");
				} else {
					sb.append("X");
				}
			}
			sb.append("\n");
		}
		return sb.toString();
	}
}

完美答案。多谢哥们。学习了

21 楼 harry_2013 2010-12-04  

只想到物理动量！

20 楼 Nanigac 2010-12-03  

提供一些逻辑，大家讨论。

①感觉是推箱子+动量守恒，每当发生箱子被推出界外，则必须再手动给予一个动量。
②还是递归来解（可能存在多个解）
手动给予任意球任意方向（4个方向）一动量，满足③的递归条件则继续迭代，否则当前无解返回。
再循环下一个球，只有到最后满足有解时才反向打出所有运动轨迹（所以每一步运动轨迹必须保存）。
③递归的条件是：
1.至少在某行（列）上存在两个或两个以上的球，且其行（列）坐标差>1
2.至少存在两个或两个以上的球，其行（列）的坐标差=1

19 楼 骨之灵魂 2010-12-03  

只想到了暴力的方法，迭代+递归每一种情况。。。。

18 楼 yunzhiyifeng 2010-12-03  

用上下左右的走递归写了个，求批。

import java.util.Random;

public class Main {
	private StringBuilder solution = new StringBuilder();

	public static void main(String[] args) {
		Main main = new Main();
		// main.doHit(main.generateTable(5, 5, 4));
		boolean[][] table = new boolean[5][5];
		table[0][0] = true;
		table[2][0] = true;
		table[3][0] = true;
		table[2][4] = true;
		table[3][0] = true;
		table[0][3] = true;
		System.out.println("table is: \n" + main.getTableString(table));
		main.doHit(table);
		if (main.solution.length() == 0) {
			System.out.println("There is not any solution");
		} else {
			main.solution.insert(0, "There is a solution.\n");
			System.out.println(main.solution.toString());
		}
	}

	public boolean[][] generateTable(int rowSize, int colSize, int nums) {
		boolean[][] table = new boolean[rowSize][colSize];
		Random random = new Random();
		while (nums != 0) {
			int x = random.nextInt(rowSize);
			int y = random.nextInt(colSize);
			if (table[x][y] == true) {
				continue;
			} else {
				table[x][y] = true;
				nums--;
			}
		}
		System.out.println("New generate table is: \n");
		System.out.println(getTableString(table));
		return table;
	}

	public boolean doHit(boolean[][] table) {
		for (int i = 0; i < table.length; i++) {
			for (int j = 0; j < table[i].length; j++) {
				if (table[i][j]) {
					if (goUp(table, i, j)) {
						return true;
					}
					if (goDown(table, i, j)) {
						return true;
					}
					if (goLeft(table, i, j)) {
						return true;
					}
					if (goRight(table, i, j)) {
						return true;
					}
				}
			}
		}
		return false;
	}

	private boolean goUp(boolean[][] table, int i, int j) {
		table = getNewCopy(table);
		boolean didHit = false;
		StringBuilder sb = new StringBuilder();
		sb.append("the ball at (").append(i).append(",").append(j).append(
				") hit the ball by up going.");
		if (i - 2 >= 0 && !table[i - 1][j]) {
			for (int k = i - 2; k >= 0; k--) {
				if (table[k][j]) {
					didHit = true;
					table[i][j] = false;
					table[k + 1][j] = true;
					table[k][j] = false;
					i = k;
				}
			}
		}
		sb.append(" After hit, the new table is:\n").append(
				getTableString(table));
		boolean result = checkAndDo(table, didHit);
		if (result) {
			solution.insert(0, sb.toString());
		}
		return result;
	}

	private boolean goDown(boolean[][] table, int i, int j) {
		table = getNewCopy(table);
		boolean didHit = false;
		StringBuilder sb = new StringBuilder();
		sb.append("the ball at (").append(i).append(",").append(j).append(
				") hit the ball by down going.");
		if (i + 2 < table.length && !table[i + 1][j]) {
			for (int k = i + 2; k < table.length; k++) {
				if (table[k][j]) {
					didHit = true;
					table[i][j] = false;
					table[k - 1][j] = true;
					table[k][j] = false;
					i = k;
				}
			}
		}
		sb.append(" After hit, the new table is:\n").append(
				getTableString(table));
		boolean result = checkAndDo(table, didHit);
		if (result) {
			solution.insert(0, sb.toString());
		}
		return result;
	}

	private boolean goLeft(boolean[][] table, int i, int j) {
		table = getNewCopy(table);
		boolean didHit = false;
		StringBuilder sb = new StringBuilder();
		sb.append("the ball at (").append(i).append(",").append(j).append(
				") hit the ball by left going.");
		if (j - 2 >= 0 && !table[i][j - 1]) {
			for (int k = j - 2; k >= 0; k--) {
				if (table[i][k]) {
					didHit = true;
					table[i][j] = false;
					table[i][k + 1] = true;
					table[i][k] = false;
					j = k;
				}
			}
		}
		sb.append(" After hit, the new table is:\n").append(
				getTableString(table));
		boolean result = checkAndDo(table, didHit);
		if (result) {
			solution.insert(0, sb.toString());
		}
		return result;
	}

	private boolean goRight(boolean[][] table, int i, int j) {
		table = getNewCopy(table);
		boolean didHit = false;
		StringBuilder sb = new StringBuilder();
		sb.append("the ball at (").append(i).append(",").append(j).append(
				") hit the ball by right going.");
		if (j + 2 < table[0].length && !table[i][j + 1]) {
			for (int k = j + 2; k < table[i].length; k++) {
				if (table[i][k]) {
					didHit = true;
					table[i][j] = false;
					table[i][k - 1] = true;
					table[i][k] = false;
					j = k;
				}
			}
		}
		sb.append(" After hit, the new table is:\n").append(
				getTableString(table));
		boolean result = checkAndDo(table, didHit);
		if (result) {
			solution.insert(0, sb.toString());
		}
		return result;
	}

	private boolean checkAndDo(boolean[][] table, boolean didHit) {
		if (isEnd(table)) {
			return true;
		} else {
			if (didHit) {
				return doHit(table);
			} else {
				return false;
			}
		}
	}

	private boolean[][] getNewCopy(boolean[][] table) {
		boolean[][] copy = table.clone();
		for (int i = 0; i < copy.length; i++) {
			copy[i] = table[i].clone();
		}
		return copy;
	}

	private boolean isEnd(boolean[][] table) {
		boolean haveOne = false;
		for (int i = 0; i < table.length; i++) {
			for (int j = 0; j < table[i].length; j++) {
				if (table[i][j] && !haveOne) {
					haveOne = true;
				} else if (table[i][j] && haveOne) {
					return false;
				}
			}
		}
		return true;
	}

	private String getTableString(boolean[][] table) {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < table.length; i++) {
			for (int j = 0; j < table[i].length; j++) {
				if (j != 0) {
					sb.append(" , ");
				}
				if (table[i][j]) {
					sb.append("O");
				} else {
					sb.append("X");
				}
			}
			sb.append("\n");
		}
		return sb.toString();
	}
}

17 楼 yj1804 2010-12-01  

编辑一下，原来写的思路有问题

16 楼 guispor7 2010-12-01  

suntao19830709 写道

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

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

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

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

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

呵呵。这个是个偷懒的办法。转个题目的空子。谢谢

15 楼 guispor7 2010-12-01  

tomorrow009 写道

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

对不起。这个没讲清楚。两个球相邻是不能动的。中间一定要有至少一个的空格。

14 楼 jinlong4696 2010-12-01  

1、一个球和两个球时问题自动解决。
2、3个球，满足两个条件有解，第一至少两个球处于同一行或同一列。第二碰撞点与第三个球处于同一行或同一列。
3、4个球：第一，至少两个球处于同一行或同一列。如果有多个组合满足情况，将所有可能情况运行一遍，此时剩三个球。判断3个球有解得条件的
4、。。。
5、
下面就是递归

13 楼 hezhou_0521 2010-12-01  

动量守恒定律。

12 楼 hezhou_0521 2010-12-01  

好像比较难，谁给出一种解法啊？

11 楼 jinlong4696 2010-12-01  

只想到穷举回溯。