|
锁定老帖子 主题：EMC笔试题（最后一道编程题）
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2010-12-03
最后修改：2010-12-03
提供一些逻辑，大家讨论。
①感觉是推箱子+动量守恒，每当发生箱子被推出界外，则必须再手动给予一个动量。 ②还是递归来解（可能存在多个解） 手动给予任意球任意方向（4个方向）一动量，满足③的递归条件则继续迭代，否则当前无解返回。 再循环下一个球，只有到最后满足有解时才反向打出所有运动轨迹（所以每一步运动轨迹必须保存）。 ③递归的条件是： 1.至少在某行（列）上存在两个或两个以上的球，且其行（列）坐标差>1 2.至少存在两个或两个以上的球，其行（列）的坐标差=1 |
| 返回顶楼 | |
|
发表时间：2010-12-04
只想到物理动量！
|
| 返回顶楼 | |
|
发表时间：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();
}
}
完美答案。多谢哥们。学习了 |
| 返回顶楼 | |
|
发表时间：2010-12-07
逆向推理 不错
|
| 返回顶楼 | |
|
发表时间：2010-12-07
觉得这个题目很绕，不非常仔细看不知道在说什么
|
| 返回顶楼 | |
|
发表时间：2010-12-08
最后修改：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是空地) |
| 返回顶楼 | |
|
发表时间：2010-12-10
玩过一个手机游戏,疯狂毛球对对碰,游戏规则跟楼主说的一模一样.
|
| 返回顶楼 | |
|
发表时间：2010-12-11
我原来的v3手机里有这个游戏，^_^
|
| 返回顶楼 | |
|
发表时间：2010-12-17
最后修改：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
}
|
| 返回顶楼 | |
|
发表时间：2011-02-14
最后修改：2011-02-14
我提供个A*算法的思路。 胡乱写了些代码在附件中
|
| 返回顶楼 | |
