九宫重排 蓝桥杯c++ 题解 字符串hash+bfs

题意：给出一个九宫格，你可以将与空格相邻的数字和空格进行交换，目的是得到另一个九宫格，问最少的步数。

思路：从最小步数不难看出我们可以使用广度优先搜索去计算最小步数，但是如何记录九宫格的状态是一个难题。我使用的方法是将九宫格看成一个长度为9的字符串，然后通过字符串hash去记录它的状态。

以下是我的字符串hash代码：

#define ll long long
ll hashh(string str){
    ll k=0,t;
    for(int i=0;i<9;i++){
	  if(str[i]=='.')t=11;
	  else t=str[i]-'0';
	  k=k*13+t;
    }
    return k;
}

hash之后得到的值可以直接用map容器进行标记，这样就可以避免搜索过的状态再重复搜索。然后我们下次bfs的时候只需要将字符串中的空格位置找出来，然后对空格的相邻的四个位置进行判断，如果合法（位置在九宫格中）且交换后的状态之前没有出现过则可以存入队列中。

通过字符串得到空格位置的代码：

  for(int i=0;i<9;i++){
    if(str[i]=='.'){
        x=i/3+1;
        y=i%3+1;
        break;
    }
}

但为了查找空格位置的四个方向更加方便，我们可以直接在用字符串得到九宫图的过程中，得到空格位置。代码如下：

            int idx=0,q[4][4];
			for(int i=1;i<=3;i++){
				for(int j=1;j<=3;j++){
					if(str[idx]=='.'){
						qq[i][j]=11;//赋值为11，是因为我字符串hash的时候空格的值给的是11。
						x=i,y=j;
					}
					else qq[i][j]=str[idx]-'0';
					idx++;
				}
			}

既然得到了空格位置，我们接下来就只需要枚举四个方向进行搜索，并重复此步骤就可得到答案。

解题代码：

#include<bits/stdc++.h>
using namespace std;
string str,str1;
#define ll long long
struct tt{
	string str;
	ll step;
	ll f;
};
ll f=0;
map<ll,int>mp;
int aa[4][2]={-1,0,0,-1,0,1,1,0};
ll hashh(string str){
    ll k=0,t;
    for(int i=0;i<9;i++){
	  if(str[i]=='.')t=11;
	  else t=str[i]-'0';
	  k=k*13+t;
    }
    return k;
}
int bfs(string str,ll w){
	tt ff;
	ff.f=w,ff.step=0,ff.str=str;
	queue<tt>q;
	q.push(ff);
	while(!q.empty()){
		tt node=q.front();
		q.pop();
		if(node.f==f){//和末尾状态相同，输出答案
			printf("%d\n",node.step);
			return 0;
		}
		else {
			int qq[10][10],x,y;
			int idx=0;
			for(int i=1;i<=3;i++){//字符串得到九宫格
				for(int j=1;j<=3;j++){
					if(node.str[idx]=='.'){
						qq[i][j]=11;
						x=i,y=j;
					}
					else qq[i][j]=node.str[idx]-'0';
					idx++;
				}
			}
			for(int i=0;i<4;i++){//枚举相邻四个位置
				int xx=x+aa[i][0];
				int yy=y+aa[i][1];
				if(xx>=1&&yy>=1&&xx<=3&&yy<=3){//判断位置是否合法
					int pp[10][10];
					int t=qq[xx][yy],ttt=qq[x][y];//记录将要交换位置的值
					ll wwe=0;
					string str="";
					for(int i=1;i<=3;i++){//得到交换后的字符串
						for(int j=1;j<=3;j++){
							if(i==xx&&j==yy){
								pp[i][j]=ttt;
								str+='.';
							}
							else if(i==x&&j==y){
								pp[i][j]=t;
								str+=pp[i][j]+'0';
							}
							else {
								pp[i][j]=qq[i][j];
								str+=pp[i][j]+'0';
							}
						}
					}
                    wwe=hashh(str);
					if(mp[wwe])continue;//此状态已经出现过直接continue
					else{
						mp[wwe]=1;//标记状态
						ff.f=wwe,ff.step=node.step+1,ff.str=str;
						q.push(ff);
					}
				}
			}
		}
	}
}
int main(){
	cin>>str;
	cin>>str1;
	ll k=hashh(str);
	mp[k]=1;
	f=hashh(str1);
	bfs(str,k);
}

第一次写博客，没写好请见谅（逃）