129 条题解

  • 1
    @ 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
    @ 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;
    }
    
    
  • 1
    @ 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
    @ 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
    @ 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
    @ 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;
    }
    
  • 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;
    }
    
  • 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;
    }
         
    
  • 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;
            
        }
                
    }
    
  • 0
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 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
    @ 2014-10-27 23:05:55

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

  • 0
    @ 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
    @ 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

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

  • 0
    @ 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
分类
搜索 | 搜索与剪枝 点击显示
标签
递交数
2282
已通过
581
通过率
25%
被复制
4
上传者