问题描述
如下面第一个图的九宫格中，放着 1~8 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成第二个图所示的局面。
我们把第一个图的局面记为：12345678.
把第二个图的局面记为：123.46758
显然是按从上到下，从左到右的顺序记录数字，空格记为句点。
本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。
输入格式
输入第一行包含九宫的初态，第二行包含九宫的终态。
输出格式
输出最少的步数，如果不存在方案，则输出-1。
样例输入
12345678.
123.46758
13524678.
46758123.
样例输出
3
22
解题思路
搜索的过程容易想，主要在于已经经过的状态的标记， map<string,int> m a p < s t r i n g , i n t > 会超时，上一年这样超时，今年还是这样，感觉一年什么都没做￣へ￣
第一种方法是将string改成int做key，即将经过的状态装换成整数来标记；
第二种方法是使用康托展开，也就是相当于一种哈希的方法了，这样开一个大概4100000的数组就可以标记了,效率也更快一些.
代码实现
map<int,int> m a p < i n t , i n t >
#include<iostream>
#include<cstring>
#include<map>
#include<cstdio>
#include<queue>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = ;
map<int, int> vis;
char str[maxn],str0[maxn],str1[maxn];
struct node{
char str[maxn];
int pos;
int step;
}temp,ne;
int ans=INF;
int tranverse(char s[])
{
int res=;
for(int i=;i<;i++){
res=(res*+(s[i]-'0'));
}
return res;
}
void BFS()
{
queue<node>qu;
int inter=tranverse(str0);
vis[inter]=;
int mark=-;
for(int i=;i<maxn;i++) {
if(str0[i]=='.'){
mark=i;
break;
}
}
strcpy(temp.str,str0);
temp.step=,temp.pos=mark;
qu.push(temp);
while(!qu.empty()){
temp=qu.front();
qu.pop();
int p=temp.pos;
if(strcmp(temp.str,str1)==){
ans=min(ans,temp.step);
continue;
}
if(temp.step>=ans){
continue;
}
if(p%!=){ //i-1
strcpy(str,temp.str);
str[p]=str[p-];
str[p-]='.';
int inter=tranverse(str);
if(!vis[inter]){
vis[inter]=;
strcpy(ne.str,str);
ne.step=temp.step+,ne.pos=p-;
qu.push(ne);
}
}
if(p%!=){ //i+1
strcpy(str,temp.str);
str[p]=str[p+];
str[p+]='.';
int inter=tranverse(str);
if(!vis[inter]){
vis[inter]=;
strcpy(ne.str,str);
ne.step=temp.step+,ne.pos=p+;
qu.push(ne);
}
}
if(p/!=){ //i+3
strcpy(str,temp.str);
str[p]=str[p+];
str[p+]='.';
int inter=tranverse(str);
if(!vis[inter]){
vis[inter]=;
strcpy(ne.str,str);
ne.step=temp.step+,ne.pos=p+;
qu.push(ne);
}
}
if(p>=){ //i-3
strcpy(str,temp.str);
str[p]=str[p-];
str[p-]='.';
int inter=tranverse(str);
if(!vis[inter]){
vis[inter]=;
strcpy(ne.str,str);
ne.step=temp.step+,ne.pos=p-;
qu.push(ne);
}
}
}
}
int main()
{
cin>>str0>>str1;
BFS();
if(ans==INF){
printf("-1\n");
}
else{
printf("%d\n",ans);
}
return ;
}
康托展开
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = ;
const int maxx =;
int fac[maxx],ans=INF;
char str[maxx],str0[maxx],str1[maxx];
bool vis[maxn];
struct node{
char str[maxx];
int step;
int pos;
}temp,ne;
void init()
{
fac[]=;
for(int i=;i<maxx;i++){
fac[i]=fac[i-]*i;
}
}
int gethash(char str[])
{
int res=;
for(int i=;i<maxx;i++){
int countt=;
for(int j=i+;j<maxx;j++){
if(str[i]>str[j]){
countt++;
}
}
res+=countt*fac[-i];
}
return res;
}
void BFS()
{
queue<node>qu;
vis[gethash(str0)]=;
int mark=-;
for(int i=;i<maxx;i++) {
if(str0[i]=='.'){
mark=i; str0[i]='0';
}
if(str1[i]=='.') str1[i]='0';
}
strcpy(temp.str,str0);
temp.step=,temp.pos=mark;
qu.push(temp);
while(!qu.empty()){
temp=qu.front();
qu.pop();
int p=temp.pos;
if(strcmp(temp.str,str1)==){
ans=min(ans,temp.step);
continue;
}
if(temp.step>=ans){
continue;
}
if(p%!=){ //i-1
strcpy(str,temp.str);
str[p]=str[p-];
str[p-]='0';
int inter=gethash(str);
if(!vis[inter]){
vis[inter]=;
strcpy(ne.str,str);
ne.step=temp.step+,ne.pos=p-;
qu.push(ne);
}
}
if(p%!=){ //i+1
strcpy(str,temp.str);
str[p]=str[p+];
str[p+]='0';
int inter=gethash(str);
if(!vis[inter]){
vis[inter]=;
strcpy(ne.str,str);
ne.step=temp.step+,ne.pos=p+;
qu.push(ne);
}
}
if(p/!=){ //i+3
strcpy(str,temp.str);
str[p]=str[p+];
str[p+]='0';
int inter=gethash(str);
if(!vis[inter]){
vis[inter]=;
strcpy(ne.str,str);
ne.step=temp.step+,ne.pos=p+;
qu.push(ne);
}
}
if(p>=){ //i-3
strcpy(str,temp.str);
str[p]=str[p-];
str[p-]='0';
int inter=gethash(str);
if(!vis[inter]){
vis[inter]=;
strcpy(ne.str,str);
ne.step=temp.step+,ne.pos=p-;
qu.push(ne);
}
}
}
}
int main()
{
init();
scanf("%s %s",str0,str1);
BFS();
printf("%d\n",ans);
return ;
}
![STL--vector容器STL—vector容器[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)