题解 - Vijos

1

^ambition LV 8 @ 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;
}

1

吴哥——传奇 LV 8 @ 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;
}

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

#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;
}

1

LCF LV 10 @ 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 head[mod],ne[maxn],to[maxn],c[maxn];
int l,r,w[4][4],tt,d[maxn],z,n,ans;

int insert(int x){
    int u=x%mod;
    for(int i=head[u];i;i=ne[i])
        if(to[i]==x) return c[i];
    to[++tt]=x; c[tt]=z+1; d[r++]=x;
    ne[tt]=head[u]; head[u]=tt;
    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);
    }
}

1

yuyilahanbao LV 10 @ 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;
}

0

Werllen LV 7 @ 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;
}

0

Bill_Yang LV 10 @ 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;
}

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

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

#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;
}

0

larryzhong LV 9 @ 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;
}

0

PowderHan LV 10 @ 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;
}

0

xudf6 LV 8 @ 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;
        
    }
            
}

0

Antinomy LV 8 @ 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;
int Head[MAXHASHSIZE], Next[MAXHASHSIZE];
State st[MAXSIZE], goal;
const int dx[] = { 0, 0, 1, -1 };
const int dy[] = { 1, -1, 0, 0 };
int dist[MAXSIZE];

void init(){
Mem(Head, 0);
}
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]);
int u = Head[h];
while (u)
{
if (memcmp(st[u], st[s], sizeof(st[u])) == 0)
return 0;
u = Next[u];
}
Next[s] = Head[h];
Head[h] = s;
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;
}
```

0

XX_XCJ LV 9 @ 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
readln(a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]);
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.

0

yaoheyuan LV 7 @ 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 head=0,end=1;
int d;
step[1]=0;
while(head<=end)
{
head++;
FOR(i,1,3) FOR(j,1,3)
{
if(i!=3)
{

swap(miao[head][i][j],miao[head][i+1][j]);
d=kanto(head);
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];} }

swap(miao[head][i][j],miao[head][i+1][j]);

}

if(j!=3)
{

swap(miao[head][i][j],miao[head][i][j+1]);
d=kanto(head);
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];}}

swap(miao[head][i][j],miao[head][i][j+1]);
}

}

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];
}

0

freeloop LV 8 @ 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行而且丑，不贴了

0

Marcha LV 7 @ 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

0

starli LV 10 @ 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;
}

0

chengchunyang LV 10 @ 2014-10-27 23:05:55

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

0

好人族 LV 9 @ 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.

0

SEX丶Elope LV 6 @ 2013-02-16 10:14:17

点击查看程序源码+详细题解

0

okyjok LV 6 @ 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判状态，速度非常快。

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

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

0

dmcgow LV 8 @ 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 + 按层扩展...

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

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

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

题解

129 条题解

算法

数据结构

技巧

基本流程

注意

晴天小猪历险记之Number

信息

状态

开发

支持

题解

129 条题解

算法

数据结构

技巧

基本流程

注意

晴天小猪历险记之Number

信息

状态

开发

支持

还没有账户？

登录