# 129 条题解

• @ 2019-02-11 23:50:48

3s左右，代码应该容易看懂

``````#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<vector>
#include<queue>
#include<map>
using namespace std;
const int factorial[]={1,1,2,6,24,120,720,5040,40320,362880}; //0-9阶乘
int a[8][9]={{2,9,4,7,5,3,6,1,8},
{2,7,6,9,5,1,4,3,8},
{4,9,2,3,5,7,8,1,6},
{4,3,8,9,5,1,2,7,6},
{6,7,2,1,5,9,8,3,4},
{6,1,8,7,5,3,2,9,4},
{8,3,4,1,5,9,6,7,2},
{8,1,6,3,5,7,4,9,2}};
int legal[8];
int in[9];
int d[2][4]={{0,0,-1,1},   //左，右，上，下
{-1,1,0,0}};
map<int,int> m;
queue<int> q;
int cantor(int *a,int n){ //cantor展开,n表示是n位的全排列，a[1~n]表示全排列的数
int ans=0,sum=0;
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++)
if(a[j]<a[i]) sum++;
ans += sum*factorial[n-i-1];
sum = 0;
}
return ans;
}
int cantor(vector<int> a,int n){ //cantor展开,参数为vector
int ans=0,sum=0;
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++)
if(a[j]<a[i]) sum++;
ans += sum*factorial[n-i-1];
sum = 0;
}
return ans;
}
vector<int> decantor(int x, int n){  //逆cantor展开  decantor(legal[i],9)
vector<int> v; //存放当前可选数
vector<int> a; //所求排列组合
for(int i=0;i<n;i++) v.push_back(i+1);
for(int i=n-1;i>=0;i--){
int r = x % factorial[i];
int t = x / factorial[i];
x = r;
sort(v.begin(),v.end());
a.push_back(v[t]);   //剩余数里第t+1个数为当前位
v.erase(v.begin()+t); //移除选作当前位的数
}
return a;
}
void getLegal(){    //获得合法目标的康拓展开值
int n=9;
for(int i=0;i<8;i++){
legal[i] = cantor(a[i],n);
}
}
void bfs(){
vector<int> cur;
int ctCur,ctNext;
while(!q.empty()){
ctCur = q.front();
cur = decantor(ctCur,9);
for(int i=0;i<9;i++){
int curx=i/3, cury= i%3;
for(int j=0;j<4;j++){
vector<int> next = cur;
int x = curx + d[0][j];
int y = cury + d[1][j];
if(x<0||x>2||y<0||y>2) continue;
swap(next[3*x+y],next[3*curx+cury]);
ctNext = cantor(next,9);
if(!m.count(ctNext)){
m[ctNext]=m[ctCur]+1;
q.push(ctNext);
}
}
}
q.pop();
}
}
int main(){
getLegal();
for(int i=0;i<8;i++){
m[legal[i]] = 0;
q.push(legal[i]);
}
bfs();
for(int n=0;n<50;n++){
for(int i=0;i<9;i++) scanf("%d",&in[i]);
cout<<m[cantor(in,9)]<<endl;
}
return 0;
}

``````
• @ 2017-08-20 00:29:30

算法
bfs
康托展开
数据结构
队列
技巧
从合法队形出发(允许我将最后他们要调到的队形称为合法队形)理由
如果从非合法队形出发bfs，那么每个队形都要搜索。搜个两三个牛一点的搜个七八个大概能行。但题目是每个测试文件50个队形。虽然每次搜索不是一定要搜索到所有的队形，但基本上接近。而从合法队形出发，则只需要搜索一次，虽然是要搜出所有的队形。但1和50大家知道怎么取舍。
如果是从非合法队形出发，那么你还要判断是否达到合法队形。这个时候你时间还需要再乘以一个数。即使你预先把正确答案的康托值算出，并且从小到大，然后逐一比较或使用了log n（n=8）的二分法查找，看是否达到。但还是乘了一个数。虽然不大，但这个……（经本人亲自实验，log n的二分在n=8的与逐一比较是一样一样的，甚至更慢） so，毫无疑问应到从合法队形出发
基本流程
初始化 base
8个合法队形入队（先用小学数学找出一个合法队形，别说你不会，然后对称呀，旋转变化，就可以得到8个，这个直接通过大脑更划算，用程序吃力不讨好）
bfs搜索，把解保存到f1中
读入，求康托值，输出对应的解
注意
限时是5秒，不是1秒
我就是没弄清这一点，使劲优化都是2.3s左右
然后在哪里使劲的优化优化呀，好悲剧呀
最后报着评测机可能比我的机子快3倍的决心试了一下，该死的忘记去掉一点本地的东西，然后无情的runtime error
再提交惊奇的发现红色的AC，基本都是2200多毫秒，就是大概2.2s多一点。不知是我家的机子快还是评测机慢？
然后仔细一看题目，发现限时5s。
顿时想死的心都有了，优化了这么久，这么久。竟然都是……

这道题做法很多，可以正向搜索，倒序搜索，双向宽搜。
但由于打表程序（如下）告诉我们出口有8个，因此最方便的还是顺序搜索。虽然后两者更快。

``````#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
int map[5][5],vst[15];
bool Check() {
for(int i=1; i<=3; i++)
if(map[i][1]&&map[i][2]&&map[i][3]&&map[i][1]+map[i][2]+map[i][3]!=15)return false;
for(int i=1; i<=3; i++)
if(map[1][i]&&map[2][i]&&map[3][i]&&map[1][i]+map[2][i]+map[3][i]!=15)return false;
if(map[1][1]&&map[2][2]&&map[3][3]&&map[1][1]+map[2][2]+map[3][3]!=15)return false;
if(map[3][1]&&map[2][2]&&map[1][3]&&map[3][1]+map[2][2]+map[1][3]!=15)return false;
return true;
}
void Dfs(int Depth) {
if(!Check())return;
if(Depth>9) {
for(int i=1; i<=3; i++) {
for(int j=1; j<=3; j++)
cout<<map[i][j]<<" ";
cout<<endl;
}
cout<<endl;
return;
}
for(int i=1; i<=9; i++)
if(!vst[i]) {
vst[i]=1;
map[(Depth-1)/3+1][(Depth-1)%3+1]=i;
Dfs(Depth+1);
vst[i]=0;
map[(Depth-1)/3+1][(Depth-1)%3+1]=0;
}
}
int main() {
Dfs(1);
return 0;
}

``````

这是打印出的出口以及对应的康拓展开的值

``````2 7 6
9 5 1
4 3 8

69074

2 9 4
7 5 3
6 1 8

77576

4 3 8
9 5 1
2 7 6

135289

4 9 2
3 5 7
8 1 6

157120

6 1 8
7 5 3
2 9 4

205759

6 7 2
1 5 9
8 3 4

227590

8 1 6
3 5 7
4 9 2

285303

8 3 4
1 5 9
6 7 2

293805

``````
``````#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int Factorial[10]= {0,40320,5040,720,120,24,6,2,1},Dirx[]= {0,1,0},Diry[]= {0,0,1};
set<int>Ans;
int vst[500005];
struct Square {
int a[4][4],step;
} Start;
int Contor(Square x) { //康托展开
int ans=0,tmp[10];
for(int i=1; i<=3; i++)
for(int j=1; j<=3; j++)
tmp[(i-1)*3+j]=x.a[i][j];
for(int i=1; i<9; i++) {
int sum=0;
for(int j=i+1; j<=9; j++)
if(tmp[j]<tmp[i])sum++;
ans+=sum*Factorial[i];
}
return ans;
}
void Bfs(int s) {
queue<Square>Q;
Q.push(Start);
vst[s]=1;
while(!Q.empty()) {
Square Now=Q.front();
Q.pop();
if(Ans.count(Contor(Now))) {
printf("%d\n",Now.step);
return;
}
for(int x=1; x<=3; x++)
for(int y=1; y<=3; y++)
for(int i=1; i<=2; i++) {
int xx=x+Dirx[i],yy=y+Diry[i];
if(xx<1||yy<1||xx>3||yy>3)continue;
Square Next=Now;
Next.step++;
swap(Next.a[x][y],Next.a[xx][yy]);
int num=Contor(Next);
if(vst[num])continue;
Q.push(Next);
vst[num]=1;
}
}
puts("-1");
}
int main() {
ios::sync_with_stdio(false);
Ans.insert(69074),Ans.insert(77576),Ans.insert(135289),Ans.insert(157120),Ans.insert(205759),Ans.insert(227590),Ans.insert(285303),Ans.insert(293805);
while(cin>>Start.a[1][1]>>Start.a[1][2]>>Start.a[1][3]) {
memset(vst,0,sizeof(vst));
for(int i=2; i<=3; i++)
for(int j=1; j<=3; j++)
cin>>Start.a[i][j];
Bfs(Contor(Start));
}
return 0;
}

``````
• @ 2016-09-27 19:57:15

暴力广搜即可。
状态数只有9!=362800种，不虚。
嗯……我好像每次把所有状态都搜了一遍，所以有点慢。

``````#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define maxn 1000010
#define mod 3000007

using namespace std;
typedef long long llg;

int l,r,w[4][4],tt,d[maxn],z,n,ans;

int insert(int x){
int u=x%mod;
if(to[i]==x) return c[i];
to[++tt]=x; c[tt]=z+1; d[r++]=x;
return 0;
}

void jie(int x){
for(int i=3;i;i--)
for(int j=3;j;j--)
w[i][j]=x%10,x/=10;
}

int ya(){
int now=0;
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
now=now*10+w[i][j];
return now;
}

void work(int x1,int y1,int x2,int y2){
swap(w[x1][y1],w[x2][y2]);
insert(ya());
swap(w[x1][y1],w[x2][y2]);
}

int main(){
File("a");
insert(816357492); insert(438951276);
insert(294753618); insert(672159834);

insert(618753294); insert(276951438);
insert(492357816); insert(834159672);

while(l!=r){
int u=d[l++]; z=insert(u); jie(u);
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++){
if(i!=3) work(i,j,i+1,j);
if(j!=3) work(i,j,i,j+1);
}
}
while(scanf("%d",&n)==1){
ans=n;
for(int i=1;i<9;i++){
scanf("%d",&n);
ans=ans*10+n;
}
printf("%d\n",insert(ans)-1);
}
}
``````
• @ 2013-12-22 10:56:25

• bfs
• 康托展开

• 队列

### 技巧

• 从合法队形出发(允许我将最后他们要调到的队形称为合法队形)理由
• 如果从非合法队形出发bfs，那么每个队形都要搜索。搜个两三个牛一点的搜个七八个大概能行。但题目是每个测试文件50个队形。虽然每次搜索不是一定要搜索到所有的队形，但基本上接近。而从合法队形出发，则只需要搜索一次，虽然是要搜出所有的队形。但1和50大家知道怎么取舍。
• 如果是从非合法队形出发，那么你还要判断是否达到合法队形。这个时候你时间还需要再乘以一个数。即使你预先把正确答案的康托值算出，并且从小到大，然后逐一比较或使用了log n（n=8）的二分法查找，看是否达到。但还是乘了一个数。虽然不大，但这个……（经本人亲自实验，log n的二分在n=8的与逐一比较是一样一样的，甚至更慢） so，毫无疑问应到从合法队形出发

### 基本流程

初始化 base
8个合法队形入队（先用小学数学找出一个合法队形，别说你不会，然后对称呀，旋转变化，就可以得到8个，这个直接通过大脑更划算，用程序吃力不讨好）
bfs搜索，把解保存到f1中
读入，求康托值，输出对应的解

### 注意

限时是5秒，不是1秒

我就是没弄清这一点，使劲优化都是2.3s左右

然后在哪里使劲的优化优化呀，好悲剧呀

最后报着评测机可能比我的机子快3倍的决心试了一下，该死的忘记去掉一点本地的东西，然后无情的runtime error

再提交惊奇的发现红色的AC，基本都是2200多毫秒，就是大概2.2s多一点。不知是我家的机子快还是评测机慢？

然后仔细一看题目，发现限时5s。

顿时想死的心都有了，优化了这么久，这么久。竟然都是……

code：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define N 362880
typedef char str[10];

str queue[N+3];
int value[N+3];
int rear,front;

int ta[] = {1,1,2,6,24,120,720,5040,40320};
int go[] = {-1,1,3,-3};

char tmps[200] ="276951438294753618438951276492357816618753294672159834816357492834159672";

int f1[N+3];
int main()
{
int i,j,k;
char s[10];
void base();
void init(char *s);
int kangtuo(char *s);
void bfs();

base(); bfs();
s[9] = 0;
for (i = 0;i < 50;i++) {
init(s);
printf("%d\n",f1[kangtuo(s)]);
}
return 0;
}

int kangtuo(char *s)
{
char static used[9];
int static i,j,k,v;
memset(used,1,sizeof(used));
for (v = k = 0;k < 8;k++,s++) {
for (j = i = 0;i < *s-'1';i++)
j += used[i];
v += j*ta[8-k]; //ta[9-k-1]
used[*s-'1'] = 0;
}
return v;
}

void init(char *s)
{
int i,k;
for (i = 0;i < 9;i++) {
scanf("%d",&k);
*(s+i) = k+'0';
}
}

void base()
{
int i,f;
memset(queue,0,sizeof(queue));
memset(value,0,sizeof(value));
for (i = 0;i < N;i++)
f1[i] = -1;
rear = front = 0;
for (i = 0;i < 8;i++) {
strncpy(queue[rear],tmps+i*9,9);
f = kangtuo(queue[rear]);
f1[f] = 0;
rear++;
}
}

int can_go(int a,int b)
{
switch (b) {
case -1:return (a%3 > 0);
case +1:return (a%3 < 2);
case -3:return (a/3 > 0);
case +3:return (a/3 < 2);
}
return 0;
}

void swap_one(int a,int b)
{
strcpy(queue[rear],queue[front]);
queue[rear][b] = queue[front][a]; queue[rear][a] = queue[front][b];
}

void bfs()
{
int i,j,f;
while (front < rear) {
if (rear > N-1)
return;
for (i = 0;i < 9;i++) {
//expand();
for (j = 0;j < 4;j++) {
if (can_go(i,go[j])) {
swap_one(i,i+go[j]);
f = kangtuo(queue[rear]);
if (f1[f] == -1) {
f1[f] = value[rear++] = value[front]+1;
}
}
}
}
front++;
}
return;
}

• @ 2019-06-23 15:05:40

用整型变量记录状态的bfs，这种小的答案空间硬刚是真的爽

``````#include <bits/stdc++.h>

using namespace std;

int ll[12]={0,1,3,4,6,7,0,1,2,3,4,5};
int rr[12]={1,2,4,5,7,8,3,4,5,6,7,8};

int tenpow[10]={1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000};

int newstate(const int& origin,int i){
int v1=(origin/tenpow[8-ll[i]])%10;
int v2=(origin/tenpow[8-rr[i]])%10;
int newone=origin-v1*tenpow[8-ll[i]]+v2*tenpow[8-ll[i]]-v2*tenpow[8-rr[i]]+v1*tenpow[8-rr[i]];
return newone;
}

int a[9];

bool issuit(int in){
for(int i=0;i<9;++i){
a[i]=(in/tenpow[i])%10;
}
if(a[0]+a[1]+a[2]!=15) return false;
if(a[3]+a[4]+a[5]!=15) return false;
if(a[6]+a[7]+a[8]!=15) return false;
if(a[0]+a[3]+a[6]!=15) return false;
if(a[1]+a[4]+a[7]!=15) return false;
if(a[2]+a[5]+a[8]!=15) return false;
if(a[0]+a[4]+a[8]!=15) return false;
if(a[2]+a[4]+a[6]!=15) return false;
return true;
}

int mysearch(){
int origin=0;
char tmpchar=0;
for(int i=0;i<9;++i){
cin>>tmpchar;
origin*=10;
origin+=(tmpchar-'0');
}
if(issuit(origin)) return 0;
queue<int> qt;
qt.push(origin);
int laynum=1;
int lay=-1;
set<int> visited;
while(!qt.empty()){
lay++;
while(laynum--){
int tmp=qt.front();
qt.pop();
for(int i=0;i<12;++i){
int newone=newstate(tmp,i);
if(issuit(newone)) return lay+1;
if(visited.find(newone)==visited.end()){
visited.insert(newone);
qt.push(newone);
}
}
}
laynum=qt.size();
}
return -1;
}

int main(){
int res[50]={0};
for(int i=0;i<50;++i){
res[i]=mysearch();
//cout<<mysearch()<<endl;
}
for(int i=0;i<50;++i){
cout<<res[i]<<endl;
}
return 0;
}

``````
• @ 2017-06-13 23:07:58

这道题做法很多，可以正向搜索，倒序搜索，双向宽搜。
但由于打表程序（如下）告诉我们出口有8个，因此最方便的还是顺序搜索。虽然后两者更快。

``````#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
int map[5][5],vst[15];
bool Check() {
for(int i=1; i<=3; i++)
if(map[i][1]&&map[i][2]&&map[i][3]&&map[i][1]+map[i][2]+map[i][3]!=15)return false;
for(int i=1; i<=3; i++)
if(map[1][i]&&map[2][i]&&map[3][i]&&map[1][i]+map[2][i]+map[3][i]!=15)return false;
if(map[1][1]&&map[2][2]&&map[3][3]&&map[1][1]+map[2][2]+map[3][3]!=15)return false;
if(map[3][1]&&map[2][2]&&map[1][3]&&map[3][1]+map[2][2]+map[1][3]!=15)return false;
return true;
}
void Dfs(int Depth) {
if(!Check())return;
if(Depth>9) {
for(int i=1; i<=3; i++) {
for(int j=1; j<=3; j++)
cout<<map[i][j]<<" ";
cout<<endl;
}
cout<<endl;
return;
}
for(int i=1; i<=9; i++)
if(!vst[i]) {
vst[i]=1;
map[(Depth-1)/3+1][(Depth-1)%3+1]=i;
Dfs(Depth+1);
vst[i]=0;
map[(Depth-1)/3+1][(Depth-1)%3+1]=0;
}
}
int main() {
Dfs(1);
return 0;
}
``````

这是打印出的出口以及对应的康拓展开的值

``````2 7 6
9 5 1
4 3 8

69074

2 9 4
7 5 3
6 1 8

77576

4 3 8
9 5 1
2 7 6

135289

4 9 2
3 5 7
8 1 6

157120

6 1 8
7 5 3
2 9 4

205759

6 7 2
1 5 9
8 3 4

227590

8 1 6
3 5 7
4 9 2

285303

8 3 4
1 5 9
6 7 2

293805
``````

那么我们就可以编出一个较快的宽搜程序了

``````#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int Factorial[10]= {0,40320,5040,720,120,24,6,2,1},Dirx[]= {0,1,0},Diry[]= {0,0,1};
set<int>Ans;
int vst[500005];
struct Square {
int a[4][4],step;
} Start;
int Contor(Square x) { //康托展开
int ans=0,tmp[10];
for(int i=1; i<=3; i++)
for(int j=1; j<=3; j++)
tmp[(i-1)*3+j]=x.a[i][j];
for(int i=1; i<9; i++) {
int sum=0;
for(int j=i+1; j<=9; j++)
if(tmp[j]<tmp[i])sum++;
ans+=sum*Factorial[i];
}
return ans;
}
void Bfs(int s) {
queue<Square>Q;
Q.push(Start);
vst[s]=1;
while(!Q.empty()) {
Square Now=Q.front();
Q.pop();
if(Ans.count(Contor(Now))) {
printf("%d\n",Now.step);
return;
}
for(int x=1; x<=3; x++)
for(int y=1; y<=3; y++)
for(int i=1; i<=2; i++) {
int xx=x+Dirx[i],yy=y+Diry[i];
if(xx<1||yy<1||xx>3||yy>3)continue;
Square Next=Now;
Next.step++;
swap(Next.a[x][y],Next.a[xx][yy]);
int num=Contor(Next);
if(vst[num])continue;
Q.push(Next);
vst[num]=1;
}
}
puts("-1");
}
int main() {
ios::sync_with_stdio(false);
Ans.insert(69074),Ans.insert(77576),Ans.insert(135289),Ans.insert(157120),Ans.insert(205759),Ans.insert(227590),Ans.insert(285303),Ans.insert(293805);
while(cin>>Start.a[1][1]>>Start.a[1][2]>>Start.a[1][3]) {
memset(vst,0,sizeof(vst));
for(int i=2; i<=3; i++)
for(int j=1; j<=3; j++)
cin>>Start.a[i][j];
Bfs(Contor(Start));
}
return 0;
}
``````
• @ 2017-05-23 23:40:34
``````#include <iostream>
#include <queue>
#include <map>
using namespace std;

int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};

struct matrix {
int arr[3][3];
bool operator < (const matrix &other) const {
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++) {
if (arr[i][j] < other.arr[i][j])
return true;
if (arr[i][j] > other.arr[i][j])
return false;
}
return false;
}
};

bool check(matrix tmp) {
if (tmp.arr[0][0] + tmp.arr[0][1] + tmp.arr[0][2] != 15) return false;
if (tmp.arr[1][0] + tmp.arr[1][1] + tmp.arr[1][2] != 15) return false;
if (tmp.arr[2][0] + tmp.arr[2][1] + tmp.arr[2][2] != 15) return false;
if (tmp.arr[0][0] + tmp.arr[1][0] + tmp.arr[2][0] != 15) return false;
if (tmp.arr[0][1] + tmp.arr[1][1] + tmp.arr[2][1] != 15) return false;
if (tmp.arr[0][2] + tmp.arr[1][2] + tmp.arr[2][2] != 15) return false;
if (tmp.arr[0][0] + tmp.arr[1][1] + tmp.arr[2][2] != 15) return false;
if (tmp.arr[0][2] + tmp.arr[1][1] + tmp.arr[2][0] != 15) return false;
return true;
}

int main() {
for (int _count = 1; _count <= 50; _count++) {
matrix start;
char ch;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
cin >> ch;
start.arr[i][j] = ch - '0';
}
}
queue<matrix> que;
map<matrix, int> steps;
que.push(start);
steps[start] = 0;
if (check(start)) {
cout << 0 << endl;
continue;
}
while (!que.empty()) {
matrix front = que.front();
que.pop();
for (int x0 = 0; x0 < 3; x0++)
for (int y0 = 0; y0 < 3; y0++)
for (int i = 0; i < 4; i++) {
int x = x0 + dx[i];
int y = y0 + dy[i];
if (x >= 0 && x < 3 && y >= 0 && y < 3) {
matrix push = front;
swap(push.arr[x0][y0], push.arr[x][y]);
if (steps.find(push) == steps.end()) {
que.push(push);
steps[push] = steps[front] + 1;
if (check(push)) {
cout << steps[push] << endl;
goto Break;
}
}
}
}
}
Break:;
}
return 0;
}
``````
• @ 2017-05-07 13:01:01
``````/*
看到这题    可能第一思路就是
对于输入的每一个数据  我们跑一边bfs找出最短操作
先不说时间复杂度    我们的目标序列有八个(手算一下就知道了)
就算是判断到达也麻烦啊虽然可以函数解决
有没有更好更快捷的方法呢？
当然是有的
我们发现其实把这个矩阵按顺序展开之后
其实就是一个1-9的全排列
所以所有的情况也不是非常多(9!=362880种)
那么与其在线查找我们不如离线查找
所以我们可以直接将八个目标状态丢进队列中
让他扩展完将所有情况的最小距离的找出来
然后读入之后直接查找就好了
这样我们只要手写一个数组模拟链表hash就好了
还是蛮简单的~
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

const int MAXN=4;
const int MOD=30000007;
struct node
{
int x;
int step;
int nxt;
};
queue<node> q;
node Hash[MOD+1];
int g[MAXN][MAXN];
int first[MOD+1];
int step=-1,tot;

int Hash_search(int x)
{
int p=x%MOD;
for(int i=first[p];i!=-1;i=Hash[i].nxt)
if(Hash[i].x==x)
return Hash[i].step;
return -1;
}

void Hash_insert(int x)
{
int p=x%MOD;
tot++;  Hash[tot].x=x;  Hash[tot].step=step+1;
Hash[tot].nxt=first[p]; first[p]=tot;
q.push(Hash[tot]);
}

void init()
{
q.push((node){816357492,0,-1});q.push((node){438951276,0,-1});
q.push((node){294753618,0,-1});q.push((node){672159834,0,-1});
q.push((node){618753294,0,-1});q.push((node){276951438,0,-1});
q.push((node){492357816,0,-1});q.push((node){834159672,0,-1});
memset(first,-1,sizeof(first));
Hash_insert(816357492); Hash_insert(438951276);
Hash_insert(294753618); Hash_insert(672159834);
Hash_insert(618753294); Hash_insert(276951438);
Hash_insert(492357816); Hash_insert(834159672);
}

int yait()
{
int ans=0;
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
ans=ans*10+g[i][j];
return ans;
}

void doit(int x)
{
for(int i=3;i>0;i--)
for(int j=3;j>0;j--)
{
g[i][j]=x%10;
x/=10;
}
}

void work(int x1,int y1,int x2,int y2)
{
swap(g[x1][y1],g[x2][y2]);
if(Hash_search(yait())==-1)
Hash_insert(yait());
swap(g[x1][y1],g[x2][y2]);
}

void bfs()
{
while(!q.empty())
{
node u=q.front();   q.pop();
doit(u.x);  step=u.step;
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
{
if(i!=3)
work(i,j,i+1,j);
if(j!=3)
work(i,j,i,j+1);
}
}
}

void out()
{
int ans,x;
while(scanf("%d",&ans)==1)
{
for(int i=1;i<=8;i++)
{
cin>>x;
ans=(ans*10)+x;
}
cout<<Hash_search(ans)<<endl;
}
}

int main()
{
init();
bfs();
out();
return 0;
}

``````
• @ 2017-04-07 17:17:53

暴力BFS

``````#include <queue>
#include <algorithm>
#include <cstdio>
#include <map>
#include <iostream>
using namespace std;
bool judge(int c[3][3])
{
for (int i = 0; i < 3; i++)
{
int sum = 0;
for (int j = 0; j < 3; j++) sum+=c[i][j];
if (sum != 15) return false;
}
for (int j = 0; j < 3; j++)
{
int sum = 0;
for (int i = 0; i < 3; i++) sum+=c[i][j];
if (sum != 15) return false;
}
int sum = c[0][0] + c[1][1] + c[2][2];
if (sum != 15) return false;
sum = c[2][0] + c[1][1] + c[0][2];
if (sum != 15) return false;
return true;
}

struct Stat
{
int c[3][3];
Stat(int _c[3][3])
{
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
{
c[i][j] = _c[i][j];
}
}
Stat(const Stat &other)
{
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
{
c[i][j] = other.c[i][j];
}
}
bool operator< (const Stat &other) const
{
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
{
if (c[i][j] < other.c[i][j]) return true;
if (c[i][j] > other.c[i][j]) return false;
}
return false;
}
};

void clear(queue <Stat> &q)
{
queue<Stat> empty;
swap(q,empty);
}

map <Stat,int> Map;
queue <Stat> que;
int main()
{
for (int Ti = 0; Ti < 50; Ti++)
{
Map.clear();
clear(que);
int orig_[3][3];
int ans = -1;
for(int i = 0; i < 3; i++)
for (int j = 0; j< 3;j++)
scanf("%1d",&orig_[i][j]);
if (judge(orig_)) ans = 0;
else
{
Stat orig(orig_);
que.push(orig);
Map[orig] = 0;
while (que.size() && ans == -1)
{
Stat s = que.front(); que.pop();
int count = Map[s];
for (int i = 0; i < 3&& ans == -1; i++)
{
for (int j = 0; j < 2; j++)
{
Stat ns(s);
swap(ns.c[i][j],ns.c[i][j+1]);
if (Map.find(ns) == Map.end())
{
if (judge(ns.c))
{
ans = count + 1;
break;
}
else
{
Map[ns] = count + 1;
que.push(ns);
}
}
}
}

for (int j = 0; j < 3&& ans == -1; j++)
{
for (int i = 0; i < 2; i++)
{
Stat ns(s);
swap(ns.c[i][j],ns.c[i+1][j]);
if (Map.find(ns) == Map.end())
{
if (judge(ns.c))
{
ans = count + 1;
break;
}
else
{
Map[ns] = count + 1;
que.push(ns);
}
}
}
}
}
}
cout << ans << endl;

}

}
``````
• @ 2016-12-06 13:58:40

测试数据 #0: Accepted, time = 2171 ms, mem = 47524 KiB, score = 10
测试数据 #1: Accepted, time = 1968 ms, mem = 47528 KiB, score = 10
测试数据 #2: Accepted, time = 1921 ms, mem = 47528 KiB, score = 10
测试数据 #3: Accepted, time = 2171 ms, mem = 47528 KiB, score = 10
测试数据 #4: Accepted, time = 1921 ms, mem = 47524 KiB, score = 10
测试数据 #5: Accepted, time = 2156 ms, mem = 47528 KiB, score = 10
测试数据 #6: Accepted, time = 2203 ms, mem = 47528 KiB, score = 10
测试数据 #7: Accepted, time = 2312 ms, mem = 47524 KiB, score = 10
测试数据 #8: Accepted, time = 1968 ms, mem = 47528 KiB, score = 10
测试数据 #9: Accepted, time = 1734 ms, mem = 47524 KiB, score = 10
Accepted, time = 20525 ms, mem = 47528 KiB, score = 100

纯暴力bfs+hash。。。想研究一下那些几百毫秒dalao的方法。。

代码
```c++
#include<iostream>
#include<iomanip>
#include<cstring>
#include<vector>
#include<sstream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<math.h>
#include<map>
#include<cctype>
#include<queue>
#include<functional>
#include<set>
#define maxn 30
#define INF 66666666
#define min(a,b) (a)>(b)?(b):(a)
#define Mem(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef int State[9];
const int MAXSIZE = 1000000;
const int MAXHASHSIZE = 1000003;
State st[MAXSIZE], goal;
const int dx[] = { 0, 0, 1, -1 };
const int dy[] = { 1, -1, 0, 0 };
int dist[MAXSIZE];

void init(){
}
int Hash(State &s){
int v = 0;
for (int i = 0; i < 9; i += 1)
v = v * 10 + s[i];
return v % MAXHASHSIZE;
}
int try_to_insert(int s){
int h = Hash(st[s]);
while (u)
{
if (memcmp(st[u], st[s], sizeof(st[u])) == 0)
return 0;
u = Next[u];
}
return 1;
}
//0 1 2
//3 4 5
//6 7 8
int judge(const State& s){
if (s[0] + s[1] + s[2] != 15)
return 0;
if (s[3] + s[4] + s[5] != 15)
return 0;
if (s[6] + s[7] + s[8] != 15)
return 0;
if (s[0] + s[3] + s[6] != 15)
return 0;
if (s[1] + s[4] + s[7] != 15)
return 0;
if (s[2] + s[5] + s[8] != 15)
return 0;
if (s[0] + s[4] + s[8] != 15)
return 0;
if (s[2] + s[4] + s[6] != 15)
return 0;
return 1;
}
int bfs(){
int front = 1, rear = 2;
init();
while (front < rear){
State & s = st[front];
if (judge(s)) return front;
for (int i = 0; i < 9; i += 1){
int x = i / 3, y = i % 3;
for (int j = 0; j < 4; j += 1){
State & t = st[rear];
memcpy(&t, &s, sizeof(s));
int nx = x + dx[j], ny = y + dy[j], nz = nx * 3 + ny;
if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3)
{
t[nz] = s[i]; t[i] = s[nz];
dist[rear] = dist[front] + 1;
if (try_to_insert(rear))
rear += 1;
}
}
}
front += 1;
}
return 0;
}
int main(){
vector<int> anses;
for (int i = 0; i < 50; i += 1){
Mem(st, 0);
Mem(Next, 0);
Mem(dist, 0);
for (int j = 0; j < 9; j += 1)
scanf("%d", &st[1][j]);
int ans = bfs();
if (ans > 0) anses.push_back(dist[ans]);
else anses.push_back(-1);
}
for (int i = 0; i < anses.size(); i += 1)
printf("%d\n", anses[i]);
return 0;
}
```

• @ 2016-09-16 09:36:26

暴力宽搜
label 10;
type rec=record q:array [1..9] of integer;bu:longint; end;
var a:array [1..9] of integer;
f:array [1..9,1..9,1..9,1..9,1..9,1..9,1..9,1..9] of boolean;
b:array [1..1000000] of rec;
i,j,k,l,n,m,t,w:longint;
procedure swap(r,t:longint);
var w:integer;
begin
w:=a[r];a[r]:=a[t];a[t]:=w;
end;
function check:boolean;
begin
check:=true;
if (a[1]+a[2]+a[3]<>15) then exit(false);
if (a[4]+a[5]+a[6]<>15) then exit(false);
if (a[7]+a[8]+a[9]<>15) then exit(false);
if (a[1]+a[4]+a[7]<>15) then exit(false);
if (a[2]+a[5]+a[8]<>15) then exit(false);
if (a[3]+a[6]+a[9]<>15) then exit(false);
if (a[1]+a[5]+a[9]<>15) then exit(false);
if (a[3]+a[5]+a[7]<>15) then exit(false);
end;
begin

for i:=1 to 50 do
begin
fillchar(f,sizeof(f),true);
if check then begin writeln('0');goto 10; end;
b[1].q:=a;
t:=1;w:=1;
f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]]:=false;
while t<=w do
begin
swap(1,2);
if f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]] then
begin
inc(w);
b[w].q:=a;
b[w].bu:=b[t].bu+1;
if check then begin writeln(b[w].bu);goto 10; end;
f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]]:=false;
end;
a:=b[t].q;
swap(1,4);
if f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]] then
begin
inc(w);
b[w].q:=a;
b[w].bu:=b[t].bu+1;
if check then begin writeln(b[w].bu);goto 10; end;
f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]]:=false;
end;
a:=b[t].q;
swap(2,3);
if f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]] then
begin
inc(w);
b[w].q:=a;
b[w].bu:=b[t].bu+1;
if check then begin writeln(b[w].bu);goto 10; end;
f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]]:=false;
end;
a:=b[t].q;
swap(2,5);
if f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]] then
begin
inc(w);
b[w].q:=a;
b[w].bu:=b[t].bu+1;
if check then begin writeln(b[w].bu);goto 10; end;
f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]]:=false;
end;
a:=b[t].q;
swap(3,6);
if f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]] then
begin
inc(w);
b[w].q:=a;
b[w].bu:=b[t].bu+1;
if check then begin writeln(b[w].bu);goto 10; end;
f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]]:=false;
end;
a:=b[t].q;
swap(4,5);
if f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]] then
begin
inc(w);
b[w].q:=a;
b[w].bu:=b[t].bu+1;
if check then begin writeln(b[w].bu);goto 10; end;
f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]]:=false;
end;
a:=b[t].q;
swap(4,7);
if f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]] then
begin
inc(w);
b[w].q:=a;
b[w].bu:=b[t].bu+1;
if check then begin writeln(b[w].bu);goto 10; end;
f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]]:=false;
end;
a:=b[t].q;
swap(5,6);
if f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]] then
begin
inc(w);
b[w].q:=a;
b[w].bu:=b[t].bu+1;
if check then begin writeln(b[w].bu);goto 10; end;
f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]]:=false;
end;
a:=b[t].q;
swap(5,8);
if f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]] then
begin
inc(w);
b[w].q:=a;
b[w].bu:=b[t].bu+1;
if check then begin writeln(b[w].bu);goto 10; end;
f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]]:=false;
end;
a:=b[t].q;
swap(6,9);
if f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]] then
begin
inc(w);
b[w].q:=a;
b[w].bu:=b[t].bu+1;
if check then begin writeln(b[w].bu);goto 10; end;
f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]]:=false;
end;
a:=b[t].q;
swap(7,8);
if f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]] then
begin
inc(w);
b[w].q:=a;
b[w].bu:=b[t].bu+1;
if check then begin writeln(b[w].bu);goto 10; end;
f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]]:=false;
end;
a:=b[t].q;
swap(8,9);
if f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]] then
begin
inc(w);
b[w].q:=a;
b[w].bu:=b[t].bu+1;
if check then begin writeln(b[w].bu);goto 10; end;
f[a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8]]:=false;
end;
a:=b[t].q;
inc(t);
end;
writeln('-1');
10:
end;
end.

• @ 2016-08-17 14:03:44

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define FOR(x,y,z) for(int x=y;x<=z;x++)
using namespace std;
int miao[1000000][4][4];
bool k[370000];
int step[1100000];
int jie[10];
int solve();
int ans[9]={0,69075,77577,135290,157121,205760,227591,285304,293806};
int kanto(int goal);
void copy(int goal1,int goal2);
int main()
{ jie[0]=1;
// freopen("1029.in","r",stdin);freopen("10291.out","w",stdout);
FOR(i,1,8) jie[i]=jie[i-1]*i;
FOR(w,1,50)
{ FOR(i,1,370000) k[i]=0;
FOR(i,1,3) FOR(j,1,3)
scanf("%d",&miao[1][i][j]);
int d =kanto(1);
k[d]=1;

int rbt=0;
FOR(i,1,9) if(d==ans[i]) {printf("0\n");rbt=1;}
if(!rbt) printf( "%d\n", solve() );

}

return 0;

}

int solve()
{
int d;
step[1]=0;
{
FOR(i,1,3) FOR(j,1,3)
{
if(i!=3)
{

if( ! k[d] )
{ end++; copy(head,end); k[d]=1; step[end]=step[head]+1;FOR(m,1,8) if(d==ans[m]) {/* FOR(q,1,3) FOR(w,1,3) printf("%d",miao[end][q][w]); printf("[]%d\n",d);*/return step[end];} }

}

if(j!=3)
{

if( !k[d] )

{ end++; copy(head,end); k[d]=1; step[end]=step[head]+1;FOR(m,1,8) if(d==ans[m]) { /* FOR(q,1,3) FOR(w,1,3) printf("%d",miao[end][q][w]); printf("[]%d\n",kanto(end));*/return step[end];}}

}

}

}

return -1;

}
int kanto(int goal)
{
int bala[10]={0,0,0,0,0,0,0,0,0,0},cc=0,d,f;
FOR(i,1,9) { f=0;
d=miao[goal][(i-1)/3+1][(i-1)%3+1]; bala[d]=1;
FOR(j,1,d) if(bala[j]==0) f++;
cc+=f*jie[9-i];
}
return cc+1;
}
void copy(int goal1,int goal2)
{
FOR( i,1,3) FOR( j,1,3) miao[goal2][i][j]=miao[goal1][i][j];
}

• @ 2016-06-07 16:05:15

第一次2700ms，没写好，第二次优化后
测试数据 #0: Accepted, time = 46 ms, mem = 5848 KiB, score = 10

测试数据 #1: Accepted, time = 46 ms, mem = 5848 KiB, score = 10

测试数据 #2: Accepted, time = 62 ms, mem = 5844 KiB, score = 10

测试数据 #3: Accepted, time = 62 ms, mem = 5844 KiB, score = 10

测试数据 #4: Accepted, time = 62 ms, mem = 5848 KiB, score = 10

测试数据 #5: Accepted, time = 46 ms, mem = 5844 KiB, score = 10

测试数据 #6: Accepted, time = 46 ms, mem = 5844 KiB, score = 10

测试数据 #7: Accepted, time = 62 ms, mem = 5844 KiB, score = 10

测试数据 #8: Accepted, time = 46 ms, mem = 5844 KiB, score = 10

测试数据 #9: Accepted, time = 62 ms, mem = 5844 KiB, score = 10

Accepted, time = 540 ms, mem = 5848 KiB, score = 100

主要思想还是和各位一样，从目标状态开始搜，不过我优化了搜的过程，因为一个解可以通过7种变换生成另外七个解，所以只需要求bfs一个，然后其他的由变换生成出来就行，另外提交区里的一万两万毫秒的是怎么回事，乱写也不会那么慢吧。。。。。
代码200行而且丑，不贴了

• @ 2016-02-27 00:37:45

我使用BFS，平均每一个测试点2s过。
太可恶了...一开始memout我废了九牛二猪之力终于控制好memeory不超了，结果又WA，我疯了似的检查代码~~~终于改好了.......~~~自己做数据一测，恩...都过，满意...于是果断提交，结果....Oh，Jesus！！！7个点AC，3个点TimelimitOut...于是我不满意地摇了摇头，优化了一下hash的时间.....终于...上帝保佑AC了~
以下是代码:
```c #include<stdio.h>//This programme was found by Lee simpson. #define maxque 363879 char hash[9][9][9][9][9][9][9][9][9]={0}; struct node{ int map[3][3]; int step; }que[363880],tmp,dd; int swp(int *a,int *b){ int temp; temp=*a; *a=*b; *b=temp; } int judans(int n){ int i,j,a=0,b=0; for(i=0;i<3;i++){ for(j=0;j<3;j++){ a+=que[n].map[i][j]; b+=que[n].map[j][i]; } if(a!=15||b!=15) return 0; a=0; b=0; } for(i=0;i<3;i++){ a+=que[n].map[i][i]; b+=que[n].map[2-i][i]; } if(a!=15||b!=15) return 0; return 1; } int judsam(int n){ dd=que[n]; if(hash[que[n].map[0][0]-1][que[n].map[0][1]-1][que[n].map[0][2]-1][que[n].map[1][0]-1][que[n].map[1][1]-1][que[n].map[1][2]-1][que[n].map[2][0]-1][que[n].map[2][1]-1][que[n].map[2][2]-1]==0) return 0; return 1; } int tip(int n){ hash[que[n].map[0][0]-1][que[n].map[0][1]-1][que[n].map[0][2]-1][que[n].map[1][0]-1][que[n].map[1][1]-1][que[n].map[1][2]-1][que[n].map[2][0]-1][que[n].map[2][1]-1][que[n].map[2][2]-1]=1; } int untip(int n){ hash[que[n].map[0][0]-1][que[n].map[0][1]-1][que[n].map[0][2]-1][que[n].map[1][0]-1][que[n].map[1][1]-1][que[n].map[1][2]-1][que[n].map[2][0]-1][que[n].map[2][1]-1][que[n].map[2][2]-1]=0; } int main(){ int i,j,k,l,g,u,v,head=0,tail=0,xx[10]={1,0,-1,0},yy[10]={0,1,0,-1},used; for(i=0;i<50;i++){ used=0; head=0; tail=0; //memset(hash,0,sizeof(hash)); for(j=0;j<3;j++) for(k=0;k<3;k++){ scanf("%d",&tmp.map[j][k]); } tmp.step=0; que[head]=tmp; tip(head); while(head<=tail){ if(judans(head)==1){ printf("%d\n",que[head].step); used=1; break; } for(l=0;l<3;l++){ for(g=0;g<3;g++){ for(u=0;u<4;u++){ if(l+xx[u]>=0&&g+yy[u]>=0&&l+xx[u]<3&&g+yy[u]<3){ tmp=que[head]; swp(&tmp.map[l][g],&tmp.map[l+xx[u]][g+yy[u]]); tmp.step++; que[maxque]=tmp; if(judsam(maxque)==0){ tip(maxque); tail++; que[tail]=tmp; } } } } } head++; } head=0; while(head<=tail){ untip(head); head++; } if(used==0){ printf("-1\n"); } } } ```
测试数据 #0: Accepted, time = 1937 ms, mem = 393800 KiB, score = 10
测试数据 #1: Accepted, time = 1765 ms, mem = 393800 KiB, score = 10
测试数据 #2: Accepted, time = 1765 ms, mem = 393800 KiB, score = 10
测试数据 #3: Accepted, time = 1890 ms, mem = 393800 KiB, score = 10
测试数据 #4: Accepted, time = 1828 ms, mem = 393800 KiB, score = 10
测试数据 #5: Accepted, time = 1968 ms, mem = 393804 KiB, score = 10
测试数据 #6: Accepted, time = 2234 ms, mem = 393800 KiB, score = 10
测试数据 #7: Accepted, time = 2171 ms, mem = 393804 KiB, score = 10
测试数据 #8: Accepted, time = 1812 ms, mem = 393804 KiB, score = 10
测试数据 #9: Accepted, time = 1687 ms, mem = 393800 KiB, score = 10
Accepted, time = 19057 ms, mem = 393804 KiB, score = 100

• @ 2015-11-03 10:14:13

首先另外写一个暴搜把所有的结果状态找出来 总共八个
然后把这八个状态压进队列 BFS一次 hash判断是否重复 这里我用了Vector比较慢……
离线查询
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
struct status{
int x,dis;
status(int x,int dis):x(x),dis(dis){}
};

const int dx[4]={3,-3,1,-1},mod=100007;
queue<status> q;
vector<int> h[100007];
int goal[60],ans[60],n=1,cnt=0;

int shl(int x,int a){
for(int i=0;i<a;i++) x*=10;
return x;
}
int shr(int x,int a){
for(int i=0;i<a;i++) x/=10;
return x;
}

void hash_insert(int x){h[x%mod].push_back(x);}
bool hash_find(int x){
int size=h[x%mod].size();
for(int i=0;i<size;i++)if(h[x%mod][i]==x) return true;
return false;
}

int main(){
freopen("1029.in","r",stdin);freopen("1029.out","w",stdout);
q.push(status(276951438,0));hash_insert(276951438);
q.push(status(294753618,0));hash_insert(294753618);
q.push(status(438951276,0));hash_insert(438951276);
q.push(status(492357816,0));hash_insert(492357816);
q.push(status(618753294,0));hash_insert(618753294);
q.push(status(672159834,0));hash_insert(672159834);
q.push(status(816357492,0));hash_insert(816357492);
q.push(status(834159672,0));hash_insert(834159672);
while(scanf("%d",&goal[n])!=EOF){
int t;
for(int i=2;i<=9;i++) scanf("%d",&t),(goal[n]*=10)+=t;n++;
}n--;
for(int i=1;i<=n;i++) ans[i]=-1;
while(!q.empty()){
status t=q.front();q.pop();
for(int i=1;i<=n;i++)
if(t.x== goal[i])
ans[i]=t.dis,cnt++;
if(cnt==n) break;
for(int i=0;i<9;i++){
for(int j=0;j<4;j++){
int tmp=t.x;
if((i==2 || i==5) && j==2) continue;
if((i==3 || i==6) && j==3) continue;
if(i+dx[j]>=0 && i+dx[j]<9){
int Claris=tmp,a1,a2;
a1=shr(Claris,i)%10;
a2=shr(Claris,i+dx[j])%10;
tmp-=shl(a1,i);tmp-=shl(a2,i+dx[j]);
tmp+=shl(a1,i+dx[j]);tmp+=shl(a2,i);
if(!hash_find(tmp)) hash_insert(tmp),q.push(status(tmp,t.dis+1));
}
}
}
}
for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
return 0;
}

• @ 2014-10-27 23:05:55

发一个我写的题解
http://blog.csdn.net/harlow_cheng/article/details/40454169
晴天小猪历险记之Number(5种写法，顺搜，逆搜，双向广搜,二叉搜索树(未加平衡树&加平衡树)

• @ 2013-10-26 20:13:01

评测结果
编译成功

测试数据 #0: Accepted, time = 1125 ms, mem = 46460 KiB, score = 10
测试数据 #1: Accepted, time = 1046 ms, mem = 46464 KiB, score = 10
测试数据 #2: Accepted, time = 1109 ms, mem = 46464 KiB, score = 10
测试数据 #3: Accepted, time = 1218 ms, mem = 46460 KiB, score = 10
测试数据 #4: Accepted, time = 1062 ms, mem = 46464 KiB, score = 10
测试数据 #5: Accepted, time = 1109 ms, mem = 46460 KiB, score = 10
测试数据 #6: Accepted, time = 1187 ms, mem = 46464 KiB, score = 10
测试数据 #7: Accepted, time = 1187 ms, mem = 46464 KiB, score = 10
测试数据 #8: Accepted, time = 1125 ms, mem = 46464 KiB, score = 10
测试数据 #9: Accepted, time = 781 ms, mem = 46464 KiB, score = 10
Accepted, time = 10949 ms, mem = 46464 KiB, score = 100

正向BFS+八维Hash=Accepted

var a:array[1..3,1..3] of longint;
b:array[1..100000,1..3,1..3] of longint;
c:array[1..9,1..9,1..9,1..9,1..9,1..9,1..9,1..9] of boolean;
s,sf,i,j,k,l,q,w,e,x,y,n,m:longint;
dd:boolean;
procedure pd(f:longint);//JianCe---------------------------------------
begin
if (b[f,1,1]+b[f,1,2]+b[f,1,3]=15)and(b[f,2,1]+b[f,2,2]+b[f,2,3]=15)
and(b[f,3,1]+b[f,3,2]+b[f,3,3]=15)and(b[f,1,1]+b[f,2,1]+b[f,3,1]=15)
and(b[f,1,2]+b[f,2,2]+b[f,3,2]=15)and(b[f,1,3]+b[f,2,3]+b[f,3,3]=15)
and(b[f,1,1]+b[f,2,2]+b[f,3,3]=15)and(b[f,3,1]+b[f,2,2]+b[f,1,3]=15)
then begin dd:=false;writeln(s);end;
end;
procedure aa(f:longint);//Hash-----------------------------------------
begin
c[b[f,1,1],b[f,1,2],b[f,1,3],b[f,2,1],b[f,2,2],b[f,2,3],b[f,3,1],
b[f,3,2]]:=true;
end;
procedure righ(x,y,z:longint);//WangYouTuoZhan-------------------------
var i,j,l,q,w,e:longint;
begin
inc(k);
for i:=1 to 3 do
for j:=1 to 3 do b[k,i,j]:=b[x,i,j];
e:=b[k,y,z];b[k,y,z]:=b[k,y,z+1];b[k,y,z+1]:=e;
if c[b[k,1,1],b[k,1,2],b[k,1,3],b[k,2,1],b[k,2,2],b[k,2,3],b[k,3,1],
b[k,3,2]] then begin dec(k);exit;end;
pd(k);aa(k);
end;
procedure down(x,y,z:longint);//WangXiaTuoZhan-------------------------
var i,j,l,q,w,e:longint;
begin
inc(k);
for i:=1 to 3 do
for j:=1 to 3 do b[k,i,j]:=b[x,i,j];
e:=b[k,y,z];b[k,y,z]:=b[k,y+1,z];b[k,y+1,z]:=e;
if c[b[k,1,1],b[k,1,2],b[k,1,3],b[k,2,1],b[k,2,2],b[k,2,3],b[k,3,1],
b[k,3,2]] then begin dec(k);exit;end;
pd(k);aa(k);
end;
begin//Main-----------------------------------------------------------
for sf:=1 to 50 do
begin
fillchar(b,sizeof(b),0); x:=1;y:=1;
fillchar(c,sizeof(c),false); s:=0;
for i:=1 to 3 do
for j:=1 to 3 do begin read(b[1,i,j]);a[i,j]:=b[1,i,j];end; dd:=true;
pd(1);aa(1);
while dd do
begin
k:=y;
inc(s);
for i:=x to y do
begin
for j:=1 to 3 do
for l:=1 to 2 do righ(i,j,l);
for j:=1 to 2 do
for l:=1 to 3 do down(i,j,l);
if not(dd) then break;
end;
x:=y+1;y:=k;
end;
end;
end.

• @ 2013-02-16 10:14:17
• @ 2012-10-23 19:42:19

├ 测试数据 01：答案正确... (0ms, 67052KB)

├ 测试数据 02：答案正确... (0ms, 67052KB)

├ 测试数据 03：答案正确... (12ms, 67052KB)

├ 测试数据 04：答案正确... (4ms, 67052KB)

├ 测试数据 05：答案正确... (4ms, 67052KB)

├ 测试数据 06：答案正确... (12ms, 67052KB)

├ 测试数据 07：答案正确... (0ms, 67052KB)

├ 测试数据 08：答案正确... (0ms, 67052KB)

├ 测试数据 09：答案正确... (20ms, 67052KB)

├ 测试数据 10：答案正确... (0ms, 67052KB)

---|---|---|---|---|---|---|---|-

Accepted / 100 / 54ms / 67052KB

对于一个3*3的矩阵，各种情况也不过9！=362880

而这里给出50个初始的乱矩阵，如果每次都正向找解，最恐怖就是50*9！=18144000，每次搜索可能经过的情况会有很多相同，不如离线操作，先记录有什么初始状态，再从初始的8个合法状态（可以事先dfs实现）进行bfs。再用了hash判状态，速度非常快。

• @ 2014-10-26 14:20:37

朋友可否把代码发给我看看，为什么我做不到那么快？

• @ 2012-10-23 19:44:38

编译通过...

├ 测试数据 01：答案正确... (0ms, 19736KB)

├ 测试数据 02：答案正确... (0ms, 19736KB)

├ 测试数据 03：答案正确... (0ms, 19736KB)

├ 测试数据 04：答案正确... (0ms, 19736KB)

├ 测试数据 05：答案正确... (0ms, 19736KB)

├ 测试数据 06：答案正确... (0ms, 19736KB)

├ 测试数据 07：答案正确... (0ms, 19736KB)

├ 测试数据 08：答案正确... (0ms, 19736KB)

├ 测试数据 09：答案正确... (0ms, 19736KB)

├ 测试数据 10：答案正确... (0ms, 19736KB)

---|---|---|---|---|---|---|---|-

Accepted / 100 / 0ms / 19736KB

SBT + 双向BFS + 按层扩展...

......优哉游哉的分割线......

• @ 2014-10-26 12:30:56

朋友，可否把代码发给我看看？我写了很久的双向BFS都是3s左右。

ID
1029

6

2586

628

24%

9