八数码难题 （codevs 1225）题解
2024-10-07 06:01:19
【问题描述】
在3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字。棋盘中留有一个空格，空格用0来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为123804765），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
【样例输入】
283104765
【样例输出】
4
【解题思路】
这题要求最少步数，因此为广度优先搜索，用队列实现。最简单的方法就是直接将每种状态存入3×3的数组中，然后将空格往四个方向移动，直至目标状态。
不过，让我们来看一看样例。
按往常来说，如果是存入3×3的数组中，那么样例中应该是 2 8 3
1 0 4
7 6 5
可是，样例却是一串数字，且中间没有空格，那么，这就给了我们一种思路，以字符串的形式存入，然后搜索，与目标状态比较时也方便一些。那么我们就换成字符串来搜索，但是字符串中要注意一下，第三位不能移到第四位，第四位不能移到第三位，因此，我们需要对该数字进行判断，看它属于哪一列，然后再搜索。
不过，这两种方式都会超时（在输出结果的步数比较大的时候），因此，我们需要判重，然而，直接开一个12345678-876543210的布尔型数组会超时，所以，这里我们用到了哈希优化。
【代码实现】
type rec=record
s:string;
s1,dep:longint;
end;
const di:array[..] of longint=(-,-,,);
c:string='';
var a:array[..] of rec;
b:string;
f,r,i,j,k,x:longint;
flag:array[..] of boolean;
procedure bfs;
var si:char;
i,j,k:longint;
begin
while f<r do
begin
inc(f);
case a[f].s1 of//判断数字属于哪一列
,,:
for i:= to do
if (a[f].s1+di[i]>=)and(a[f].s1+di[i]<=) then
begin
inc(r);
a[r]:=a[f];
a[r].s[a[r].s1]:=a[r].s[a[r].s1+di[i]];
a[r].s[a[r].s1+di[i]]:='';
a[r].s1:=a[r].s1+di[i];
inc(a[r].dep);
val(a[r].s,x);
if not(flag[x mod ]) then
dec(r)
else
begin
flag[x mod ]:=false;
if a[r].s=c then
begin
writeln(a[r].dep);
halt;
end;
end;
end;
,,:
for i:= to do
if (a[f].s1+di[i]>=)and(a[f].s1+di[i]<=) then
begin
inc(r);
a[r]:=a[f];
a[r].s[a[r].s1]:=a[r].s[a[r].s1+di[i]];
a[r].s[a[r].s1+di[i]]:='';
a[r].s1:=a[r].s1+di[i];
inc(a[r].dep);
val(a[r].s,x);
if not(flag[x mod ]) then
dec(r)
else
begin
flag[x mod ]:=false;
if a[r].s=c then
begin
writeln(a[r].dep);
halt;
end;
end;
end;
,,:
for i:= to do
if (a[f].s1+di[i]>=)and(a[f].s1+di[i]<=) then
begin
inc(r);
a[r]:=a[f];
a[r].s[a[r].s1]:=a[r].s[a[r].s1+di[i]];
a[r].s[a[r].s1+di[i]]:='';
a[r].s1:=a[r].s1+di[i];
inc(a[r].dep);
val(a[r].s,x);
if not(flag[x mod ]) then
dec(r)
else
begin
flag[x mod ]:=false;
if a[r].s=c then
begin
writeln(a[r].dep);
halt;
end;
end;
end;
end;
end;
end;
begin
fillchar(flag,sizeof(flag),true);
readln(a[].s);
for i:= to do
if a[].s[i]='' then
begin
a[].s1:=i;
break;
end;
f:=;r:=;
bfs;
end.
最新文章
- Spring的jdbcTemplate查询执行原生sql
- 使用USRP探索无线世界 Part 1：USRP从入门到追踪飞机飞行轨迹
- 自动化脚本过程中出现This element neither has attached source nor attached Javadoc...的解决方法
- hdu Train Problem I
- MAC OS下免费下载YouTube
- 1074: [SCOI2007]折纸origami - BZOJ
- 如何提高Web服务端并发效率的异步编程技术
- ZJOI2009 狼和羊的故事
- Hibernate中对象的3种状态：瞬时态、持久态、脱管态
- 调色板QPalette类用法详解（附实例、源码）
- AHOI2009最小割
- sqlplus常用操作命令2
- Docker最全教程——数据库容器化之持久保存数据（十一）
- Linux下使用yum安装软件命令
- Mvc Swagger报错的解决办法。
- windows环境安装phantomjs和pyspider遇到的问题
- Net Core平台灵活简单的日志记录框架NLog+SqlServer初体验
- SpringBoot整合Rabbitmq设置消息请求头
- Luogu4697 CEOI2011 Balloons 单调栈
- ADB not responding