2005年百度之星程序设计大赛试题总决赛题目
2005年百度之星程序设计大赛试题总决赛题目
题目描述：
八方块移动游戏要求从一个含 8 个数字（用 1-8 表示）的方块以及一个空格方块（用 0 表示）的 3x3 矩阵的起始状态开始，不断移动该空格方块以使其和相邻的方块互换，直至达到所定义的目标状态。空格方块在中间位置时有上、下、左、右 4 个方向可移动，在四个角落上有 2 个方向可移动，在其他位置上有 3 个方向可移动。例如，假设一个 3x3 矩阵的初始状态为：
8 0 3
2 1 4
7 6 5
目标状态为：
1 2 3
8 0 4
7 6 5
则一个合法的移动路径为：
8 0 3 8 1 3 8 1 3 0 1 3 1 0 3 1 2 3
2 1 4 => 2 0 4 => 0 2 4 => 8 2 4 => 8 2 4 => 8 0 4
7 6 5 7 6 5 7 6 5 7 6 5 7 6 5 7 6 5
另外，在所有可能的从初始状态到目标状态的移动路径中，步数最少的路径被称为最短路径；在上面的例子中，最短路径为 5 。如果不存在从初试状态到目标状态的任何路径，则称该组状态无解。
请设计有效的（细节请见评分规则）算法找到从八方块的某初试状态到某目标状态的所有可能路径中的最短路径，并用 C/C++ 实现。
输入数据：
程序需读入已被命名为 start.txt 的初始状态和已被命名为 goal.txt 的目标状态，这两个文件都由 9 个数字组成（ 0 表示空格， 1-8 表示 8 个数字方块），每行 3 个数字，数字之间用空格隔开。
输出数据：
如果输入数据有解，输出一个表示最短路径的非负的整数；如果输入数据无解，输出 -1 。
自测用例：
如果输入为： start.txt 和 goal.txt ，则产生的输出应为：
5
又例，如果用
7 8 4
3 5 6
1 0 2
替换 start.txt 中的内容，则产生的输出应为：
21
评分规则：
1 ）我们将首先使用和自测用例不同的 10 个 start.txt 以及相同的 goal.txt ，每个测试用例的运行时间在一台 Intel Xeon 2.80GHz 4 CPU/ 6G 内存的 Linux 机器上应不超过 10 秒（内存使用不限制），否则该用例不得分；
2 ）每个选手的总分（精确到小数点后 6 位） =10 秒钟内能产生正确结果的测试用例数量 x10+ （ 1/ 产生这些正确结果的测试用例的平均运行毫秒 ) ；
3 ）如果按此评分统计仍不能得出总决赛将决出的一、二、三等奖共计九名获奖者，我们将先设 N=2 ，然后重复下述过程直至产生最高的 9 位得分：用随机生成的另外 10 个有解的 start.txt 再做测试，并对这 10*N 个测试用例用 2 ）中公式重新计算总分， N++ 。
基本方法：
1.由初始图，初始0位置，我用1-9个位置，放置0-8个数字，连成字符串路：8|0|3|2|1|4|7|6|5 来描述这些
图形，
2.通过移动0，寻找可以互换的位置，可以产生许多新的图形，例路：由0初始位置，寻找可以移动的位置，把这些位置，放入一个数组，以便循环处理
3.我用链记录了0不同的移动，产生的路径，以及图型变化路线，通过路径可以判断来路，上次0的位置，在寻找新位置时，不能回走来路点，而通过记录的新产生的图形，通过一个图形集合数组，过滤重复的图形，因为移动0，当变化为已有图形时，那么这个链以后的移动就会和其他有相同图的链效果相同，扩大了分支，通过过滤，过滤放到过滤数组，只使用一条记录这种状态图的链，当遇到满足条件时，保存；
4.放到过滤数组$sequ的链还有用的，就是可以通过与满足条件的链对比，看是否有相同的图，路过有，说明可以通过换一部分路径以实现多种路径，代码里我没有做这部分德处理，只提取了第一条满足条件的转换路径
PHP代码：
set_time_limit(0);
/*
初始图：8 0 3 目标图： 1 2 3
2 1 4 8 0 4
7 6 5 7 6 5
*/
//1-9 编号，对应 位置数组0-8
//echo str_pad("",10000);
//ob_start();
$kstu='8|0|3|2|1|4|7|6|5';//初始图
$jstu='1|2|3|8|0|4|7|6|5';//目标图
$kongwz=0;
$arr=explode('|',$kstu);
for($i=0;$i
if($arr[$i]==0){$kongwz=$i+1;break;}
}//确定0的初始位置2
echo '当前的原始图：'.$kstu.'；目标图：'.$jstu.'
';
echo '原始0位置：'.$kongwz.'
';
$tustr=$kstu;//每步的图-连成的字符串
$movestr=$kongwz;//移0的字符串，-连
$lian=$tustr.'#'.$movestr;//移动0和形成的图的字符串集
$lianarr=array($lian);
$sequ=array($lian);//舍弃重复部分，减少处理量，这部分最后可以和满足条件的数组做比较，有相同图的，可以通过相应位置互换，以达到获得多种路径
$tuji=array($kstu);//图的集合，过滤重复，只增加新图
$save=array();//保存成功移动到目标图的链数组
$jishu=0;
$end=0;
while(!empty($lianarr)&&$end!=1){
//echo 'while
';
$newarr=array();
//循环每条可用链
for($i=0;$i
//echo 'i
';
$lian=$lianarr[$i];
$a1=explode('#',$lian);
$tustr=$a1[0];//图字符串
$movestr=$a1[1];
$tuarr=explode('-',$tustr);//图的数组
$movearr=explode('-',$movestr);//移动的数组
$len1=count($tuarr)-1;
$len2=count($movearr)-1;
$nowtu=$tuarr[$len1];//当前图
$nowwz=$movearr[$len2];//当前0的位置，1-9编号
//根据图的宽高，寻找上下左右的可移点 宽：3，高3
$kuan=3;//宽
$gao=3;//高
$kego=array();//装载可移动的位置
//向上取，$nowwz-宽>0,取，否不取
if($nowwz-$kuan>0)$kego[]=$nowwz-$kuan;
//向下取，$nowwz+宽
取
if(($nowwz+$kuan)
//向左取，$nowwz-1%$kuan!=0取
if(($nowwz-1)%$kuan!=0)$kego[]=$nowwz-1;
//向右取，$nowwz+1%宽！=1取
if(($nowwz+1)%$kuan!=1)$kego[]=$nowwz+1;
//end 设置可移位置数组
//开始取各个位置
for($i1=0;$i1
//路过移位有上一步，判断，不能移回上一步
if($len1>0){
if($kego[$i1]==$movearr[$len1-1])continue;
}
//echo 'i1
';
$newmovestr=$movestr.'-'.$kego[$i1];
//互换位置
$t=explode('|',$nowtu);
$t1=$t[$nowwz-1];
$t[$nowwz-1]=$t[$kego[$i1]-1];
$t[$kego[$i1]-1]=$t1;
$newtu=implode('|',$t);//生成新的图
$newlian=$tustr.'-'.$newtu.'#'.$newmovestr;//新一条的总链
//判断是否新图是目标图，是记录在save里
if($newtu==$jstu){$save[]=$newlian;$end=1;break;}
else{
if(in_array($newtu,$tuji)){
//路过在图集里，记录链，放到舍弃数组
$sequ[]=$newlian;
}//end if(in_array($newtu,$tuji)
else{
$tuji[]=$newtu;
$newarr[]=$newlian;
}
}//end 不是目标图
}//end for($i1=0;$i1
}//end for($i=0;$i
$jishu++;
$lianarr=$newarr;
}//end while(!empty($lianarr))
echo '得到的第一个移位：（说明：#右边：0的移动路径；#左边:随着0移动，产生的位置的图的变化路径，- 分割每个位置的图，与0的移动路径一一对应）
';
print_R($save);
?>
测试结果;用百度给的测试，速度很快，可以修改，初始图，目标图测试，有些转换可能要时间长些，我试过几个，能在10秒以内吧