Eight HDU-1043 (bfs)
Eight
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 35625 Accepted Submission(s): 9219
Special Judge
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 x
where the only legal operation is to exchange 'x' with one of the tiles with which it shares an edge. As an example, the following sequence of moves solves a slightly scrambled puzzle:
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
5 6 7 8 5 6 7 8 5 6 7 8 5 6 7 8
9 x 10 12 9 10 x 12 9 10 11 12 9 10 11 12
13 14 11 15 13 14 11 15 13 14 x 15 13 14 15 x
r-> d-> r->
The letters in the previous row indicate which neighbor of the 'x' tile is swapped with the 'x' tile at each step; legal values are 'r','l','u' and 'd', for right, left, up, and down, respectively.
Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable version of the puzzle, and
frustrating many people. In fact, all you have to do to make a regular puzzle into an unsolvable one is to swap two tiles (not counting the missing 'x' tile, of course).
In this problem, you will write a program for solving the less well-known 8-puzzle, composed of tiles on a three by three
arrangement.
1 2 3
x 4 6
7 5 8
is described by this list:
1 2 3 x 4 6 7 5 8
#include <iostream>
#include <queue>
#include <cstring>
#include <cstdio>
#include <string>
#include <algorithm>
#include <set>
#include <map> using namespace std; map<string, char> mp; // 存储当前局面和方向
map<string, string>pre; // 存储当前局面和上一局面 int flag = ; struct node
{
int cur; // x在string中的下标
string s; // 当前局面
}nod; string Swap(string s, int x, int y)
{
swap(s[x], s[y]);
return s;
} void Print(string str) // 递归打印结果
{
if(mp[str] == '#')
return;
Print(pre[str]);
cout << mp[str];
} void bfs()
{
queue<node> Q; Q.push(nod);
mp[nod.s] = '#'; node p,t;
while(!Q.empty())
{
p = Q.front();
Q.pop(); if(p.s == "12345678x")
{
flag = ;
Print("12345678x");
} for(int i = ; i < ; ++i)
{
if(i == ) // 向左
{
if(p.cur % != ) // 下标为0,3,6的不能向左移动
{
t.s = Swap(p.s, p.cur, p.cur-);
if(mp.count(t.s) == )
{
mp[t.s] = 'l';
pre[t.s] = p.s;
t.cur = p.cur - ;
Q.push(t);
} }
}
else if(i == ) // 向右
{
if(p.cur % != ) // 下标为2,5,8的不能向右移动
{
t.s = Swap(p.s, p.cur, p.cur+);
if(mp.count(t.s) == )
{
mp[t.s] = 'r';
pre[t.s] = p.s;
t.cur = p.cur + ;
Q.push(t);
} }
}
else if(i == ) // 向上
{
if(p.cur > ) // 下标为0,1,2的不能向上移动
{
t.s = Swap(p.s, p.cur, p.cur-);
if(mp.count(t.s) == )
{
mp[t.s] = 'u';
pre[t.s] = p.s;
t.cur = p.cur - ;
Q.push(t);
} }
}
else if(i == ) // 向下
{
if(p.cur < ) // 下标为6,7,8的不能向下移动
{
t.s = Swap(p.s, p.cur, p.cur+);
if(mp.count(t.s) == )
{
mp[t.s] = 'd';
pre[t.s] = p.s;
t.cur = p.cur + ;
Q.push(t);
}
}
} }
}
} int main()
{ char c;
string str;
int k;
for(int i = ; i < ; ++i)
{
cin >> c;
str += c;
if(c == 'x')
k = i; // 记录x的初始下标
} nod.s = str;
nod.cur = k; bfs();
if(flag == )
cout << "unsolvable";
cout << endl; return ;
}
最新文章
- clover 在win10下工作不正常
- 【转】OPENGL基本API概述
- ruby + watir 自动化上传图片文件解决方案
- 想要愉快入住酒店?缺了它还真不行!(含PPT)
- Android中空格及换行
- 使用PHPExcel报错 Fatal error: Class &#39;ZipArchive&#39; not found
- Ubuntu 14.04远程登录服务器--openssh的安装和配置简明步骤
- CDN云主机与传统虚拟主机功能对比
- stack 集合栈计算机 (摘)
- cornerstone the working copy is locked due to a previous文件lock解决办法
- 对web.config加密,和解密码详细说明
- JVM基础(4)-编译
- 性能测试平台效率优化的一次经验(python版)
- 最长上升子序列(LIS) dp学习~3
- 【Unity3D】Unity3D开发《我的世界》之七、番外篇
- Xshell与虚拟机不能正常连接
- 【开源】OSharpNS,轻量级.net core快速开发框架发布
- JSOI2019 Round2 极限生还
- Spring Boot 启动:No active profile set, falling back to default profiles: default
- nginx的proxy_pass路径转发规则最后带/问题