阅读量:0
目录
题目描述
The 15-puzzle has been around for over 100 years; even if you don't know it by that name, you've seen it. It is constructed with 15 sliding tiles, each with a number from 1 to 15 on it, and all packed into a 4 by 4 frame with one tile missing. Let's call the missing tile 'x'; the object of the puzzle is to arrange the tiles so that they are ordered as:
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.输入
You will receive, several descriptions of configuration of the 8 puzzle. One description is just a list of the tiles in their initial positions, with the rows listed from top to bottom, and the tiles listed from left to right within a row, where the tiles are represented by numbers 1 to 8, plus 'x'. For example, this puzzle
1 2 3
x 4 6
7 5 8
is described by this list:
1 2 3 x 4 6 7 5 8输出
You will print to standard output either the word ``unsolvable'', if the puzzle has no solution, or a string consisting entirely of the letters 'r', 'l', 'u' and 'd' that describes a series of moves that produce a solution. The string should include no spaces and start at the beginning of the line. Do not print a blank line between cases.
样例
输入
2 3 4 1 5 x 7 6 8
输出
ullddrurdllurdruldr
题解
样例解释
对于输入为
2 3 4 1 5 x 7 6 8
换为二维数组为
2 3 4
1 5 x
7 6 8
要求找到还原为
1 2 3
4 5 6
7 8 x
的路径，并输出路径
r为x向右交换一个，l为x向左交换一个，u为x向上交换一个，d为x向下交换一个
交换过程如下
2 3 4 2 3 x 2 x 3 x 2 3 1 2 3 1 2 3 1 2 3 1 2 3
1 5 x—u—>1 5 4—l—>1 5 4—l—>1 5 4—d—>x 5 4—d—>7 5 4—r—>7 5 4—u—>7 x 4
7 6 8 7 6 8 7 6 8 7 6 8 7 6 8 x 6 8 6 x 8 6 5 8
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3—r—> 7 4 x—d—> 7 4 8—l—>7 4 8—l—>7 4 8—u—>x 4 8—r—>4 x 8—d—>4 6 8
6 5 8 6 5 x 6 x 5 x 6 5 7 6 5 7 6 5 7 x 5
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3—r—>4 6 8—u—>4 6 x—l—>4 x 6—d—>4 5 6—r—>4 5 6
7 5 x 7 5 8 7 5 8 7 x 8 7 8 x
最后路径为
ullddrurdllurdruldr
一共19步
另外对于路径是不唯一的
所以输出任意答案即可
例如，这也是一个答案
ldruullddrurdllurrd
此题为传统的八数码问题只有，只输入九个字符
考虑将输入的九个字符拼接成一个字符串，再根据字符在字符串中的位置，计算出在二维数组中的位置
例如
1 2 3 4 5 6 7 8 x
行数为3，列数为3
对应的二维数组为
1 2 3
4 5 6
7 8 x
其中
1在下标为0的位置，对应二维数组中的(0,0)，行数0/3=0，列数0%3=0
2在下标为1的位置，对应二维数组中的(0,1)，行数1/3=0，列数1%3=1
3在下标为2的位置，对应二维数组中的(0,2)，行数2/3=0，列数2%3=2
4在下标为3的位置，对应二维数组中的(1,0)，行数3/3=1，列数3%3=0
5在下标为4的位置，对应二维数组中的(1,1)，行数4/3=1，列数4%3=1
6在下标为5的位置，对应二维数组中的(1,2)，行数5/3=1，列数5%3=2
7在下标为6的位置，对应二维数组中的(2,0)，行数6/3=2，列数6%3=0
8在下标为7的位置，对应二维数组中的(2,1)，行数7/3=2，列数7%3=1
x在下标为8的位置，对应二维数组中的(2,2)，行数8/3=2，列数8%3=2
每次找到x的位置，在二维数组中上下左右进行交换即可
注意：
此题是多组样例，故每次都bfs进行一次查找必然会超时
于是考虑到终点状态始终为
1 2 3
4 5 6
7 8 x
于是可以从终点开始，寻找能到达的状态，然后将其储存起来，如果没被储存必然是复原不了的
由于是逆向搜索
对于
1 2 3 1 2 3
4 5 6 到 4 x 5
7 8 x 7 8 6
很明显对于终点状态到起点状态x应该先上移再左移为ul
而对于起点到终点x应该先右移再下移为rd
所以对于逆向搜索的路径与正向搜索相比正向搜索的上下左右对应逆向搜索的下上右左
最后应该翻转
但是还存在一个问题，如下代码Memory Limit Exceeded，内存超限了
#include<iostream> #include<queue> #include<map> using namespace std; map<string,int>bj; map<string,string>ans; queue<pair<string,string>>qwer; string ks="",js=""; int cnt=0; int dx[]={-1,0,1,0}; int dy[]={0,-1,0,1}; void bfs() { qwer.push({js,""}); bj[js]=1; while(!qwer.empty()) { auto t=qwer.front(); qwer.pop(); if(!ans.count(t.first)) { ans[t.first]=t.second; } int q=t.first.find("x"); int x=q/3,y=q%3; for(int i=0;i<4;i++){ int a=x+dx[i],b=y+dy[i]; if(a>=0&&a<=2&&b>=0&&b<=2) { auto str=t; swap(str.first[q],str.first[a*3+b]); if(!bj.count(str.first)) { bj[str.first]=1; if(i==0) { qwer.push({str.first,t.second+"d"}); } if(i==1) { qwer.push({str.first,t.second+"r"}); } if(i==2) { qwer.push({str.first,t.second+"u"}); } if(i==3) { qwer.push({str.first,t.second+"l"}); } } } } } } int main() { string cs; js="12345678x";//终点状态 bfs(); while(cin>>cs) { ks=""; ks+=cs; for(int i=1;i<9;i++){ cin>>cs; ks+=cs; } if(!ans.count(ks)) { cout<<"unsolvable"<<endl; } else { cout<<ans[ks]<<endl; } } }
康托展开
由于使用map映射导致内存超限，我们引入康托展开
对于一个字符串12345
有5!=5*4*3*2*1=120种排列方式
按照字典序从小到大开始排
字典序最小的12345编号为1
字典序最大的54321编号为2
这样就保证了一个编号对应一个状态
因此可以使用一维数组来存储
计算编号
举个例子
求45231的编号
45231
当前位置为4，所以当前位置选1，2，3的字符串无论后4位怎么排列，都比当前字符串的字典序小
即3*4!=72
45231
当前位置为5，所以当前位置选1，2，3，我们不再看前面选过的数所以不选4，当前位置无论后3位怎么排列，都比当前字符串的字典序小
即3*3!=18
45231
当前位置为2，所以当前位置选1，当前位置无论后2位怎么排列，都比当前字符串的字典序小
即1*2!=2
45231
当前位置为3，所以当前位置选1，当前位置无论后1位怎么排列，都比当前字符串的字典序小
即1*1!=1
45231
当前位置为1后面没有任何数了
即0*0!=0
所以45231的编号为72+18+2+1=93
可以使用编号93来表示这个状态
代码：
/*这题使用map映射会导致内存超限，通过康德展开可以减少空间的使用*/ #include<iostream> #include<algorithm> #include<queue> using namespace std; const int N=4e5+7;//需要9!个编号表示所有的状态 int haxi[N];//用一维数组的下标来表示每一个状态 string ans[N]; queue<string>qwer; string ks="",js=""; int cnt=0; int dx[]={-1,0,1,0}; int dy[]={0,-1,0,1}; int jc[]={0,1,2,6,24,120,720,5040,40320};//预处理阶层 int cantuo(string s) { //计算在此之前，还有多少个字典序比当前字符串小的字符串的个数 int cnt; int sum=0; for(int i=0;i<8;i++){ cnt=0; for(int j=i+1;j<9;j++) if(s[i]>s[j]) //记录后面有几个比当前小的(让他们排到当前位置，此时无论如何字典序都比当前字符串小) cnt++; sum+=(jc[8-i]*cnt); //当前位置后面的几位可以用剩下的数排列(因为当前位置为比当前字符小的字符，所以后面无论怎么排都比当前字符串的字典序小) } return sum; } void bfs() { int jsq=cantuo(js); qwer.push(js); haxi[jsq]=1; ans[jsq]=""; while(!qwer.empty()) { auto t=qwer.front(); qwer.pop(); int q=t.find("x");//找到x的位置 int x=q/3,y=q%3;//转换为对应的二维数组坐标 for(int i=0;i<4;i++){ int a=x+dx[i],b=y+dy[i]; if(a>=0&&a<=2&&b>=0&&b<=2) { auto str=t; swap(str[q],str[a*3+b]);//尝试移动 int de=cantuo(str); int cs=cantuo(t); if(!haxi[de]) { haxi[de]=1; ans[de]=ans[cs];//上一个状态的路径，加上当前需要的操作，即为这个状态的操作路径 if(i==0) { ans[de]+="d";//逆推,因此(-1,0)对应向下d qwer.push(str); } if(i==1) { ans[de]+="r";//逆推,因此(0,-1)对应向下d qwer.push(str); } if(i==2) { ans[de]+="u";//逆推,因此(1,0)对应向上u qwer.push(str); } if(i==3) { ans[de]+="l";//逆推,因此(0,1)对应向左l qwer.push(str); } } } } } } int main() { string cs; js="12345678x"; bfs();//从终点开始找防止超时，因为是多组样例 while(cin>>cs) { ks=""; ks+=cs; for(int i=1;i<9;i++){ cin>>cs; ks+=cs; } int t=cantuo(ks); if(!haxi[t]) { cout<<"unsolvable"<<endl; } else { string ss=ans[t]; reverse(ss.begin(),ss.end());//逆序操作要翻转 cout<<ss<<endl; } } }
