游戏每一关，都是由5行7列的方块组成。有固定不动的方块，有可以移动的若干不同方块。将这些方块同时移动到各自的指定位置才算赢。移动时有个特点，比如往上移动一步，所有可移动方块都会同时移动一格，但如果上面是边缘或是有方块堵着了就不会移动。具体玩法，有空的可以去下载试玩一下^_^
我抽空就用php写了最佳算法的代码，但遇到一点百思不得其解的问题。
不过现在问题已经解决了，逻辑没有问题，是判断游戏结束的代码写错了，想当然地认为是那样的，检查几遍都没去细看，结果就是出错在那里。
哈哈，感觉这个例子用来面试或者锻炼新手比较好！
下面贴上自己的实现代码，已经可以用了：
<?php
define('ASC', 1); // 正向排序
define('DESC', 0); // 逆向排序
define('MOVE_UP', 1); // 上移
define('MOVE_DOWN', 2); // 下移
define('MOVE_LEFT', 3); // 左移
define('MOVE_RIGHT', 4); // 右移
define('ROW', 5); // 地图有 5 排
define('COL', 7); // 地图有 7 列
// memory_limit，单个线程最大内存，为 -1 则不限制
// 会影响数组的最大长度
ini_set('memory_limit', -1);
// max_execution_time，最大响应时间，为 0 则不限制
// 有些地图的计算时间可能超过默认的30秒
ini_set('max_execution_time', 0);
// 地图数据
$mapArr = array(
// 第 2 章，第 1 关
// 最少步数：17，下 左 左 左 左 上 上 上 上 下 左 右 右 下 左 上 右
array(
'base' => array('1112215152' => 9),
'box' => array('25' => 1, '45' => 2),
'end' => array('44' => 1, '24' => 2),
),
// 第 2 章，第 2 关
// 最少步数 16，左 上 右 右 下 左 下 下 左 左 上 右 右 右 右 右
array(
'base' => array('44' => 9),
'box' => array('14' => 1, '54' => 2, '3335' => 3),
'end' => array('27' => 1, '41' => 2),
),
);
// 参数 a 用来指定地图
$a = isset($_GET['a']) ? $_GET['a'] - 1 : 0;
// 参数 s 用来决定循环次数
$s = isset($_GET['s']) ? $_GET['s'] : 0;
//初始化地图关卡
$map = new Map($mapArr[$a]);
//开始，计算出一个最少移动方案
$game = new Game($map);
$game->start($s);
/**
* 关卡地图类
*/
class Map {
//固定不动的方块。二位数组，角标即坐标
public $base = array();
//可移动方块(包括不需要对位的方块)。二位数组，角标即坐标
public $box = array();
//需要对齐的方块。二位数组，角标即坐标
public $end = array();
public function __construct($gameMap = array()) {
foreach ($gameMap as $key => $value) {
if (!empty($value)) {
$this->$key = $this->createBoxArr($value);
}
}
}
private function createBoxArr($map = array()) {
$arr = array();
foreach ($map as $key => $value) {
$tmp = str_split($key, 2);
foreach ($tmp as $k => $v) {
list($row, $col) = str_split($v, 1);
$arr[$row][$col] = $value;
}
}
return $arr;
}
}
/**
* 存储最简移动方案的类
*/
class Step {
public $steps = array();
public function getSteps() {
$step_str = str_replace(array(MOVE_UP, MOVE_DOWN, MOVE_LEFT, MOVE_RIGHT), array('上', '下', '左', '右'), $this->steps);
return array_reduce($step_str, 'arr2str');
}
}
/**
* 数组到字符串的转换函数
*/
function arr2str($val_a, $val_b) {
return $val_a . " " . $val_b;
}
/**
* 游戏主类
*/
class Game {
// 最简方案，键名为移动后的位置对应的md5值，键值即为最短步长
public $minStepBoxArray = array();
// 每次移动后的结束位置，即为下次移动时的所有起步位置
public $startBoxArray = array();
// 每次移动后的最简方案，即为下次移动前的所有已移动的最简方案
public $stepObjArray = array();
// 步长
public $count = 0;
// 方块地图
public $map = null;
// 游戏结束标识
private $gameEnd = false;
public function __construct($map = null) {
$this->map = $map;
}
/**
* 从移动第1步开始计算，直到循环结束
* 存储所有最简方案到 $minStepBoxArray
* 存储每次移动的起步位置到 $startBoxArray
* 存储每次移动的最简方案到 $stepObjArray
*/
public function start($total = 0) {
$t0 = $this->runTime();
while (true) {
$this->count++;
// 结束判断
if ($this->gameEnd === true) {
break;
}
if ($total != 0 && $this->count > $total) {
break;
}
if ($this->count > 1 && empty($this->stepObjArray)) {
break;
}
// 初始化此次移动的所有起步位置和各自对应的最简方案
$startArray = $this->startBoxArray ? $this->startBoxArray : array($this->map->box);
$stepsArray = $this->stepObjArray ? $this->stepObjArray : array(new Step);
// 开始计算本次移动的最简方案
$t1 = $this->runTime();
$this->startBoxArray = array();
$this->stepObjArray = array();
foreach ($startArray as $key => $box) {
$step = $stepsArray[$key];
// 每个起步位置都要移动
$this->move($box, $step);
}
$t2 = $this->runTime();
echo '第 ' . $this->count . ' 次循环，得出 ' . sizeof($this->stepObjArray) . ' 种 ' . $this->count . ' 步长的最简方案，总计最简方案 ' . sizeof($this->minStepBoxArray) . ' 种， 用时： ' . ($t2 - $t1) . ' 秒，' . $this->count . ' 次循环总用时：' . ($t2 - $t0) . ' 秒<br>';
}
}
private function runTime() {
$mtime = microtime();
list($ten_thousand, $sec) = explode(" ", $mtime);
return ((float)$ten_thousand + (float)$sec);
}
/**
* 移动方法，可以有 上 下 左 右 四个方向
*/
private function move($box, $step) {
$this->moveUp($box, $step);
$this->moveDown($box, $step);
$this->moveLeft($box, $step);
$this->moveRight($box, $step);
ob_flush();
}
/**
* 向上移动一步，将活动方块的数组 竖直方向 正向 排序
*/
private function moveUp($box, $step) {
$this->sortBox($box, array('col' => ASC));
$this->moveBox($box, $step, MOVE_UP);
}
/**
* 向下移动一步，将活动方块的数组 竖直方向 逆向 排序
*/
private function moveDown($box, $step) {
$this->sortBox($box, array('col' => DESC));
$this->moveBox($box, $step, MOVE_DOWN);
}
/**
* 向左移动一步，将活动方块的数组 水平方向 正向 排序
*/
private function moveLeft($box, $step) {
$this->sortBox($box, array('row' => ASC));
$this->moveBox($box, $step, MOVE_LEFT);
}
/**
* 向右移动一步，将活动方块的数组 水平方向 逆向 排序
*/
private function moveRight($box, $step) {
$this->sortBox($box, array('row' => DESC));
$this->moveBox($box, $step, MOVE_RIGHT);
}
/**
* 将可移动的方块按 方向规则 重新排序
* 主要是考虑到移动方块时会被前面的方块堵住的情况
*/
private function sortBox(&$box, $sort = array()) {
$_sort = array('col' => ASC, 'row' => ASC);
$_sort = $sort ? array_merge($_sort, $sort) : $_sort;
$_sort['col'] === ASC ? ksort($box) : krsort($box);
foreach ($box as $key => & $value) {
$_sort['row'] === ASC ? ksort($value) : krsort($value);
}
}
/**
* 按方向移动方块，并尝试添加一步，判断尝试结果
*/
private function moveBox($box, $step, $move) {
$_box = $box;
// 遍历每一个方块，判断是否移动
foreach ($box as $k1 => $v1) {
foreach ($v1 as $k2 => $v2) {
if (empty($v2)) {
continue;
}
switch ($move) {
case MOVE_UP:
if ($k1 > 1 && empty($this->map->base[$k1 - 1][$k2]) && empty($_box[$k1 - 1][$k2])) {
$_box[$k1 - 1][$k2] = $v2;
unset($_box[$k1][$k2]);
}
break;
case MOVE_DOWN:
if ($k1 < ROW && empty($this->map->base[$k1 + 1][$k2]) && empty($_box[$k1 + 1][$k2])) {
$_box[$k1 + 1][$k2] = $v2;
unset($_box[$k1][$k2]);
}
break;
case MOVE_LEFT:
if ($k2 > 1 && empty($this->map->base[$k1][$k2 - 1]) && empty($_box[$k1][$k2 - 1])) {
$_box[$k1][$k2 - 1] = $v2;
unset($_box[$k1][$k2]);
}
break;
case MOVE_RIGHT:
if ($k2 < COL && empty($this->map->base[$k1][$k2 + 1]) && empty($_box[$k1][$k2 + 1])) {
$_box[$k1][$k2 + 1] = $v2;
unset($_box[$k1][$k2]);
}
break;
}
}
}
// 克隆本次移动方案
$_step = clone $step;
// 尝试添加一步，若为最简方案则添加
$result = $this->tryToAddStep($_step, $_box, $move);
// 判断游戏是否结束
if ($result === true) {
$this->gameEnd = true;
echo '************************************<br>';
echo '最少步数：' . $this->count . '<br>';
echo $_step->getSteps() . '<br>';
echo '************************************<br>';
} else {
$_step = null;
unset($_step);
}
}
/**
* 尝试添加一步，若为最简方案则添加
*/
private function tryToAddStep($step, $box, $move) {
$md5Box = $this->md5Box($box);
// 步长大于等于已有步长的方案，不是最简方案或重复，将被忽略
if (!empty($this->minStepBoxArray[$md5Box]) && $this->minStepBoxArray[$md5Box] <= $this->count) {
return false;
}
// 组成此次步长下的最简方案
$step->steps[] = $move;
// 添加新的最简方案或更新已有的最简方案，键名为移动后的位置对应的md5值，键值即为当前步长
$this->minStepBoxArray[$md5Box] = $this->count;
// 添加本次移动的结束位置，即为下次移动时的所有起步位置
$this->startBoxArray[$md5Box] = $box;
// 添加本次移动的最简方案，即为下次移动前的所有已移动的最简方案
$this->stepObjArray[$md5Box] = clone $step;
// 判断是否已移动到结束位置
$gameEnd = true;
foreach ($this->map->end as $k1 => $v1) {
foreach ($v1 as $k2 => $v2) {
if (empty($box[$k1][$k2]) || $box[$k1][$k2] !== $v2) {
$gameEnd = false;
break;
}
}
}
return $gameEnd;
}
/**
* 生成所有最简方案的md5唯一标识，作为数组的键名
*/
private function md5Box($box) {
// 先排序
$this->sortBox($box);
$str = "minStepBoxArray:";
foreach ($box as $k1 => $v1) {
foreach ($v1 as $k2 => $v2) {
if (empty($v2)) {
continue;
}
$str.= $k1 . ":" . $k2 . ":\"" . $v2 . "\",";
}
}
return md5($str);
}
} 最佳答案
