问题 1426: [蓝桥杯][历届试题]九宫重排

解法一：

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<cstring>
#include<cstdio>
#define M 1000000
using namespace std;
 
typedef int type[9];
type qs[M];
type mb;
int front,rear;
int dir[4][2]={-1,0,0,-1,0,1,1,0};
int dis[M]={0};
set<int> vis;
int panchong(int x)
{
	int i,sum=0;
	for (i=0; i<9; i++)
	{
		sum = sum*10+qs[x][i];
	}
	if (vis.count(sum))
	{
		return 0;
	}
	vis.insert(sum);
	return 1;
}
int bfs()
{
	front = 1;
	rear = 2;
	int i,j,k=0,c,x,y,xx,yy,z,zz;
	while (front < rear)
	{
		type &s = qs[front];
		if (memcmp(s,mb,sizeof(mb)) == 0)
		{
			return front;
		}
		for (k=0; k<9; k++)
		{
			if(s[k]==0)
            {
                z=k;
            }
		}
		x = z/3;
		y = z%3;
		for (i=0; i<4; i++)
		{
			xx = x+dir[i][0];
			yy = y+dir[i][1];
			if(xx>=0 && xx<3 && yy>=0 && yy<3)
			{
				type &t = qs[rear];
				memcpy(t,s,sizeof(s));
				zz=xx*3+yy;
				t[z] = s[zz];
				t[zz] = s[z];
				if(panchong(rear))
				{
					dis[rear] = dis[front]+1;
					rear++;
				}
			}
		}
		front++;
	}
	return -1;
}
int main()
{
	int i,j,cnt;
	char ch[10],ch2[10];
	scanf("%s %s",ch,ch2);
	for (i=0; i<9; i++)
	{
		if(ch[i]<='8'&&ch[i]>='0')
            qs[1][i]=ch[i]-'0';
        else
            qs[1][i]=0;
	}
	for (i=0; i<9; i++)
	{
		if(ch2[i]<='8'&&ch2[i]>='0')
            mb[i]=ch2[i]-'0';
        else
            mb[i]=0;
	}
	cnt = bfs();
	if(cnt>0)
	{
		cout<<dis[cnt]<<endl;
	 }
	 else
	 {
	 	cout<<-1<<endl;
	 }
	return 0;
}

解法二

总的来说题意就是看两个字符串经过最少多少步能成为相同的，我是用广搜做的，有上下左右四个方向，把把两个位置的数字和’.'调换，看和想要的字符串是否相同，用map记录字符串是否出现过，这样只要搜到就一定是最短的。结果很不幸的超时了。最后用了双向BFS，把尾部的字符串也加入队列，同时搜索，用maps标记字符串是否出现过，如果是从初态转化而来，标记为1，如果是从终态转化而来，标记为2，用temp来记录步数，当双方有交替的时候就证明搜索成功。

#include <bits/stdc++.h>
using namespace std;
const int N = 10;
char a[N], b[N];
int nex[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};
map<string, int>maps;
map<string, int>temp;
int BFS()
{
	if(strcmp(a, b)==0)
		return 0;
	queue<string>q;
	q.push(a);
	q.push(b);
	while(!q.empty()) {
		string head = q.front();
		q.pop();
		int x, y, t;
		for(int i=0; i<3; i++)
			for(int j=0; j<3; j++) {
				t = i*3+j;
				if(head[t]=='.') {
					x=i;
					y=j;
					break;
				}
			}
		t=x*3+y;
		for(int i=0; i<4; i++) {
			int tx = x+nex[i][0];
			int ty = y+nex[i][1];
			
			if(tx>=0 && tx<3 && ty>=0 && ty<3) {
				int r=tx*3+ty;
				string tail = head;
				tail[t] = tail[r];
				tail[r] = '.';
				if(!maps[tail]) {
					maps[tail] = maps[head];
					temp[tail] = temp[head]+1;
					q.push(tail);
				}
				else if(maps[head]+maps[tail]==3){
					return temp[head]+temp[tail]+1;
				}
			}
		}	
		
	}
	return -1;
}
int main()
{
	scanf("%s%s", a, b);
	maps[a]=1;
	maps[b]=2;
	printf("%d\n", BFS());
	return 0;
}