guispor7
- 浏览: 26123 次
- 性别:
- 来自: 上海
-
最新评论
-
c581698：
感谢分享
JAVA中四个二进制位从操作符即（&按位与、|按位货、^按位异或、~按位取反） -
mm4409092：
android listview综合使用示例_结合数据库操作和 ...
android：处理ListView的条目长按事件 -
prettyinsight：
<p>小弟用swing写了个演示程 ...
EMC笔试题（最后一道编程题） -
prettyinsight：
<p>我提供个A*算法的思路。 ...
EMC笔试题（最后一道编程题） -
regular：
<pre name="code" c ...
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 # # # # #
# # # # # # #
# # # # # # #
# # # # # # #
# # # # # # #
两个球相邻是不能动的。中间一定要有至少一个的空格。
当碰撞过后，只有一个球在棋盘上为有解。否则无解。
每次选择任意一个球开始运动，碰撞完成后，可以选择任意剩下小球开始运动。
请写出一个程序，任意初始化棋盘上的小球，然后判断是否有解，有解打印出球移动步骤，否则输入无解。
完美答案。多谢哥们。学习了
呵呵。这个是个偷懒的办法。转个题目的空子。谢谢
对不起。这个没讲清楚。两个球相邻是不能动的。中间一定要有至少一个的空格。
题目是这样的：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>
<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>
<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以内的计算~
匆匆写的，没咋写注释而且很多判断应该还可以归并。。大致写个意思吧。。呵呵，勿喷勿喷。。。另外就现在的数据来说无解的情况比较多。。呵呵。。(O是球，X是空地)
我来个另类的吧，性能应该相对好一点，尤其是没有每次都克隆一堆数组。用的位操作，理论上说应该支持递归深度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
①感觉是推箱子+动量守恒，每当发生箱子被推出界外，则必须再手动给予一个动量。
②还是递归来解（可能存在多个解）
手动给予任意球任意方向（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皇后的即可。
这样其实比较容易。以前看到有的游戏不会创建无解的初始位置，相信通过这种方式比较容易实现。
但是这个题目并没有限定死，任意初始化棋盘上的小球，然后判断是否有解，有解打印出球移动步骤，否则输入无解。
关键这个任意并不是要输出全部的。我们完全可以模拟一种“伪任意”，可以按照下面偷个巧。
按下面步骤：
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位置不变，并认定为有解呢？
即： 假如最后剩下两个相邻小球， b1(1,2) , b2(2,2), 那么是否可以使用b1撞走b2,而b1位置不变，并认定为有解呢？
对不起。这个没讲清楚。两个球相邻是不能动的。中间一定要有至少一个的空格。
14 楼
jinlong4696
2010-12-01
1、一个球和两个球时问题自动解决。
2、3个球，满足两个条件有解，第一至少两个球处于同一行或同一列。第二碰撞点与第三个球处于同一行或同一列。
3、4个球：第一，至少两个球处于同一行或同一列。如果有多个组合满足情况，将所有可能情况运行一遍，此时剩三个球。判断3个球有解得条件的
4、。。。
5、
下面就是递归
2、3个球，满足两个条件有解，第一至少两个球处于同一行或同一列。第二碰撞点与第三个球处于同一行或同一列。
3、4个球：第一，至少两个球处于同一行或同一列。如果有多个组合满足情况，将所有可能情况运行一遍，此时剩三个球。判断3个球有解得条件的
4、。。。
5、
下面就是递归
13 楼
hezhou_0521
2010-12-01
动量守恒定律。
12 楼
hezhou_0521
2010-12-01
好像比较难，谁给出一种解法啊？
11 楼
jinlong4696
2010-12-01
只想到穷举回溯。
发表评论
相关推荐
EMC笔试题面经整理EMC笔试题面经整理EMC笔试题面经整理
此次笔试共分为四个部分：信息收集、多项选择题、编程题以及开放性问题。考试时间限定为3小时，不允许使用任何电子设备辅助答题。 #### 信息收集部分解析 这一部分主要是为了收集应聘者的个人偏好信息，包括工作...
而编程题部分则有四个，其中两个难度较低，另外两个则相当具有挑战性。作者举了一个例子，即在给出的一个单向链表中找出倒数第k个节点，这要求应聘者必须具备扎实的编程基础和高效解决问题的能力。 写作题要求用...
EMC2009校园招聘笔试题答案,c++实现，可编译运行
EMC面试笔试必备的知识点涵盖了多个方面，包括但不限于以下几个关键领域： 1. 存储基础： - 存储层次结构：理解主存、辅助存储和外部存储之间的区别，以及它们如何协同工作以提高数据访问效率。 - 存储类型：了解...
这份“北京华为经典笔试题（附答案）”汇集了华为笔试中出现频率较高的试题，涉及的领域包括但不限于编程、网络、操作系统、数据结构和算法。这些试题的设计既符合华为公司对员工技术素养的高要求，又具有一定的难度...
同时，还有对应聘者提供的招聘流程、笔试题、面试经验、面试题目和面试感受等信息。这些内容对于想要了解EMC招聘流程和面试技巧的求职者非常有价值。 通过上述知识点，我们可以看出EMC是一个在存储技术领域具有深厚...
【EMC2007笔试题】涉及到的是EMC公司2007年针对软件质量工程师一职的招聘笔试环节。EMC是一家知名的全球信息技术公司，主要提供数据存储、信息安全、云计算等解决方案。在这样的笔试中，考生可以期待遇到与软件测试...
【EMC2010年校园招聘笔试题】是一份极具价值的历史资料，它记录了全球知名存储解决方案提供商EMC在2010年面向校园招聘时所使用的测试题目。对于那些希望进入EMC工作的求职者，这份资料具有很高的参考价值，能够帮助...
根据给定的EMC 2007应届生笔试题的内容，我们可以从中提取出一些重要的知识点，并对其进行详细的解析。 ### 一、考试说明与规则 #### 1. 考试时间 - 考生需在**3小时内**完成整个考试。 #### 2. 考试结构 - **总...
1. **编程题限制**： 在提供的代码示例中，题目要求编写一个函数`p(int i, int N)`，该函数要在一行内完成输出i到N以及N到i的数字，并且每个数字占一行。此外，还有一些特殊的限制条件： - 只允许有一个语句，即一...