30 条题解

  • 0
    @ 2018-04-26 17:24:25

    #1 Accepted 566ms 46.0 MiB
    #2 Accepted 579ms 46.094 MiB
    #3 Accepted 578ms 46.168 MiB
    #4 Accepted 533ms 46.105 MiB
    #5 Accepted 552ms 46.125 MiB
    #6 Accepted 540ms 46.0 MiB
    #7 Accepted 575ms 46.004 MiB
    #8 Accepted 595ms 46.094 MiB
    #9 Accepted 421ms 46.113 MiB
    #10 Accepted 272ms 46.105 MiB

    按照现在的评测及配置,还是这样的通过速度,我猜当年的题目,暴力BFS是肯定会超时的。
    一定需要进行减枝,最简单的减枝就是达成了目标后,后续的状态如果已经超过了这个步数,就直接跳过

    状态 耗时 内存占用

    #1 Accepted 44ms 28.0 MiB
    #2 Accepted 430ms 44.098 MiB
    #3 Accepted 12ms 23.5 MiB
    #4 Accepted 507ms 46.0 MiB
    #5 Accepted 208ms 34.0 MiB
    #6 Accepted 499ms 46.125 MiB
    #7 Accepted 459ms 46.0 MiB
    #8 Accepted 498ms 46.062 MiB
    #9 Accepted 452ms 46.0 MiB
    #10 Accepted 421ms 44.105 MiB

    事实证明加了这个减枝,只能好转,但并不治本。可能当时需要额外的减枝,估计需要一个估价值,选取更靠近答案的节点有限搜索

  • 0
    @ 2018-02-04 22:03:31

    直接暴力BFS

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <queue>
    #include <tuple>
    
    using namespace std;
    
    constexpr int maxN = (int)1e6;
    constexpr int pow10[] = {1, 10, 100, 1000, 10000, 100000, 1000000};
    
    int dist[6][maxN];
    int src, dest;
    
    //  5  4  3  2  1  0
    //     -fr-     -bk-
    //     |  |     |  |
    //  X  X  X  X  X  X
    //  |        |
    // d0       dp
    //          pos=2 in this example
    int swap0(int val, int pos)
    {
        if (pos == 5)
            return -1;
    
        int d0 = val / pow10[5];
        int dp = val / pow10[pos] % 10;
    
        return val + (dp - d0) * pow10[5] - (dp - d0) * pow10[pos];
    }
    
    //  5  4  3  2  1  0
    //  -fr-     -bk-
    //  |  |     |  |
    //  X  X  X  X  X  X
    //        |        |
    //       dp       d5
    //       pos=3 in this example
    int swap1(int val, int pos)
    {
        if (pos == 0)
            return -1;
    
        int d5 = val % 10;
        int dp = val / pow10[pos] % 10;
    
        return val + (d5 - dp) * pow10[pos] - (d5 - dp);
    }
    
    //  5  4  3  2  1  0
    //  -fr-     --bk---
    //  |  |     |     |
    //  X  X  X  X  X  X
    //        |
    //        d
    //        pos=3 in this example
    int up(int val, int pos)
    {
        int d = val / pow10[pos] % 10;
        if (d == 9)
            return -1;
    
        return val + pow10[pos];
    }
    
    int down(int val, int pos)
    {
        int d = val / pow10[pos] % 10;
        if (d == 0)
            return -1;
    
        return val - pow10[pos];
    }
    
    int bfs()
    {
        if (src == dest)
            return 0;
    
        memset(dist, -1, sizeof(dist));
        dist[5][src] = 0;
    
        queue<pair<int, int>> que;
        que.emplace(src, 5);
        int curV, curP;
        int nextV, nextP;
    
        while (!que.empty())
        {
            tie(curV, curP) = que.front();
            que.pop();
    
            pair<int, int> nextS[] {{swap0(curV, curP), curP},
                                    {swap1(curV, curP), curP},
                                    {curV, curP - 1},
                                    {curV, curP + 1},
                                    {up(curV, curP), curP},
                                    {down(curV, curP), curP}};
            for (auto& pr: nextS)
            {
                tie(nextV, nextP) = pr;
                if (nextV != -1 && nextP >= 0 && nextP <= 5 && dist[nextP][nextV] == -1)
                {
                    dist[nextP][nextV] = dist[curP][curV] + 1;
                    que.emplace(nextV, nextP);
                    if (nextV == dest)
                        return dist[nextP][nextV];
                }
            }
        }
        return -1;
    }
    
    int main()
    {
        scanf("%d%d", &src, &dest);
        printf("%d\n", bfs());
        return 0;
    }
    
  • 0
    @ 2016-09-29 21:45:03

    const
    maxl=6000000;
    type
    statetype=array[1..6] of longint;
    nodetype=record
    state:statetype;
    point,step:longint;
    end;
    var
    q:array[1..maxl] of nodetype;
    app:array[1..6,0..9,0..9,0..9,0..9,0..9,0..9] of boolean;
    st,start,closed:statetype;
    i,tail,j,head,sp,pt,code:longint;
    s:string;
    function compare(var x,y:statetype;l:longint):boolean;
    var
    i:longint;
    begin
    compare:=true;
    for i:=1 to l do
    if x[i]<>y[i] then exit(false);
    end;
    begin

    read(s);
    j:=pos(' ',s);
    for i:=1 to j-1 do
    val(s[i],start[i],code);
    delete(s,1,j);
    for i:=1 to length(s) do
    val(s[i],closed[i],code);
    j:=0;

    fillchar(app,sizeof(app),false);
    head:=0;
    tail:=1;
    q[tail].state:=start;
    q[tail].point:=1;
    q[tail].step:=0;
    while head<>tail do
    begin
    inc(head);
    if head>maxl then head:=1;

    sp:=q[head].step;
    pt:=q[head].point;
    st:=q[head].state;

    if compare(st,closed,6) then
    begin
    writeln(sp);
    exit;
    end
    else
    begin
    if (pt>1)and(not app[pt-1,st[1],st[2],st[3],st[4],st[5],st[6]])then
    begin
    inc(tail);
    if tail>maxl then tail:=1;

    q[tail].state:=st;
    q[tail].step:=sp+1;
    q[tail].point:=pt-1;
    app[pt-1,st[1],st[2],st[3],st[4],st[5],st[6]]:=true;
    end;

    if (pt<6)and(not app[pt+1,st[1],st[2],st[3],st[4],st[5],st[6]]) then
    begin
    inc(tail);
    if tail>maxl then tail:=1;
    q[tail].state:=st;
    q[tail].step:=sp+1;
    q[tail].point:=pt+1;
    app[pt+1,st[1],st[2],st[3],st[4],st[5],st[6]]:=true;
    end;

    if st[pt]<9 then
    begin
    st[pt]:=st[pt]+1;
    if not app[pt,st[1],st[2],st[3],st[4],st[5],st[6]]
    then
    begin
    inc(tail);
    if tail>maxl then tail:=1;
    q[tail].state:=st;
    q[tail].step:=sp+1;
    q[tail].point:=pt;
    app[pt,st[1],st[2],st[3],st[4],st[5],st[6]]:=true;
    end;
    st[pt]:=st[pt]-1;
    end;
    if st[pt]>0 then
    begin
    st[pt]:=st[pt]-1;
    if not app[pt,st[1],st[2],st[3],st[4],st[5],st[6]]
    then
    begin
    inc(tail);
    if tail>maxl then tail:=1;
    q[tail].state:=st;
    q[tail].step:=sp+1;
    q[tail].point:=pt;
    app[pt,st[1],st[2],st[3],st[4],st[5],st[6]]:=true;
    end;
    st[pt]:=st[pt]+1;
    end;

    i:=st[1];
    j:=st[pt];

    st[1]:=j;
    st[pt]:=i;
    if not app[pt,st[1],st[2],st[3],st[4],st[5],st[6]]
    then
    begin
    inc(tail);
    if tail>maxl then tail:=1;
    q[tail].state:=st;
    q[tail].step:=sp+1;
    q[tail].point:=pt;
    app[pt,st[1],st[2],st[3],st[4],st[5],st[6]]:=true;
    end;

    st[1]:=i;
    st[pt]:=st[6];
    st[6]:=j;
    if not app[pt,st[1],st[2],st[3],st[4],st[5],st[6]]
    then
    begin
    inc(tail);
    if tail>maxl then tail:=1;
    q[tail].state:=st;
    q[tail].step:=sp+1;
    q[tail].point:=pt;
    app[pt,st[1],st[2],st[3],st[4],st[5],st[6]]:=true;
    end;
    end;
    end;
    end.
    //可以用with do来优化;
    之前自己挖了一个坑,就是st是全局数组,改变了状态没有复原;
    可以写双向搜索,再加一个用位置+数值的估价函数来优化深搜(不过建议还是写成宽搜的);

  • 0
    @ 2016-08-14 17:41:30
    #include <iostream>
    #include <map>
    #include <string>
    #include <queue>
    #include <cstring>
    using namespace std;
    struct state
    {
        int step;
        string s;
    };
    string e;
    state st;
    map<string,int> my;
    queue<state> q;
    int bfs()
    {
        state t,tt; string ss; int i;
        q.push(st);  my[st.s]=1; //Init
        while(!q.empty())
        {
            t=q.front(); q.pop();
    
            for(ss=t.s,i=0;i<6;i++)
                if(ss[i]!=e[i]) break;
            if(i==6) return t.step;
            ss=t.s; swap(ss[0],ss[ss[6]-'0']);
            if(!my.count(ss))
            {
                tt.s=ss; tt.step=t.step+1;
                q.push(tt); my[ss]=1;
            }
            ss=t.s; swap(ss[5],ss[ss[6]-'0']);
            if(!my.count(ss))
            {
                tt.s=ss; tt.step=t.step+1;
                q.push(tt); my[ss]=1;
            }
            ss=t.s; if(ss[ss[6]-'0']!='9'&&ss[ss[6]-'0']!=e[ss[6]-'0']) ss[ss[6]-'0']+=1;
            if(!my.count(ss))
            {
                tt.s=ss; tt.step=t.step+1;
                q.push(tt); my[ss]=1;
            }
            ss=t.s; if(ss[ss[6]-'0']!='0'&&ss[ss[6]-'0']!=e[ss[6]-'0']) ss[ss[6]-'0']-=1;
            if(!my.count(ss))
            {
                tt.s=ss; tt.step=t.step+1;
                q.push(tt); my[ss]=1;
            }
            ss=t.s;
            if(ss[6]-'0'!=0)
            {
                if(ss[6]!='5')
                {
                    if(ss[ss[6]-'0']==e[ss[6]-'0']) ss[6]-=1;
                }
                else ss[6]-=1;
            }
            if(!my.count(ss))
            {
                tt.s=ss; tt.step=t.step+1;
                q.push(tt); my[ss]=1;
            }
            ss=t.s;
            if(ss[6]-'0'!=5)
            {
                if(ss[6]!='0')
                {
                    if(ss[ss[6]-'0']==e[ss[6]-'0']) ss[6]+=1;
                }
                else ss[6]+=1;
            }
            if(!my.count(ss))
            {
                tt.s=ss; tt.step=t.step+1;
                q.push(tt); my[ss]=1;
            }
        }
    }
    int main()
    {
        cin>>st.s>>e;
         my.clear();
         st.s+='0'; st.step=0;
         printf("%d",bfs());
    }
    

    和楼下的时间比差远了

  • 0
    @ 2016-05-04 00:02:40

    0 ms 576 KIB
    ......纯粹的人工剪枝......深刻体会到所谓暴力出奇迹......

    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<cmath>
    #define MAXN 10000000
    using namespace std;

    int now;
    int minn=MAXN;
    int ans=MAXN;
    int use[2][6];
    int poi=0;

    int tmp;

    inline void s0(int x){int t=use[0][0];use[0][0]=use[0][x];use[0][x]=t;}
    inline void s1(int x){int t=use[0][5];use[0][5]=use[0][x];use[0][x]=t;}

    bool check()
    {
    for(int i=0;i<6;i++)
    if(use[0][i]!=use[1][i])
    return false;
    return true;
    }

    int abs(int x)
    {return x>0? x:-x;}

    int one[7];
    int cnt[10];

    void dfs(int poi,int num,int yi)
    {///*
    if(check())
    {ans=min(ans,num-1)/*,printf("%d: %d\n",poi,ans)*/;return ;}//*/
    int t1,t2,t3,plus;
    if(poi==5)
    {
    if(use[0][0]!=use[1][0])plus=abs(use[0][5]-use[1][0])+1+abs(use[0][0]-use[1][5]);
    else plus=abs(use[1][5]-use[0][5]);
    ans=min(ans,num+plus);
    return ;
    }

    if(poi==0)
    {
    // zhi chuan
    dfs(poi+1,num+1,yi);
    // huan chuan
    s1(poi);
    dfs(poi+1,num+2,yi);
    s1(poi);
    // bian chuan
    t1=use[0][0];
    plus=abs(use[0][0]-use[1][0]);
    use[0][0]=use[1][0];
    dfs(poi+1,num+plus+1,1);
    use[0][0]=t1;
    // huan bian chuan
    t1=use[0][0];t2=use[0][5];
    s1(poi);
    plus=abs(use[0][0]-use[1][0])+1;
    use[0][0]=use[1][0];
    dfs(poi+1,num+plus+1,1);
    use[0][0]=t1,use[0][5]=t2;
    // bian huan chuan
    t1=use[0][0],t2=use[0][5];
    plus=abs(use[0][0]-use[1][5])+1;
    use[0][0]=use[0][5],use[0][5]=use[1][5];
    dfs(poi+1,num+plus+1,yi);
    use[0][0]=t1,use[0][5]=t2;
    // bian huan bian chuan
    t1=use[0][0],t2=use[0][5];
    plus=abs(use[0][0]-use[1][5])+1+abs(use[0][5]-use[1][0]);
    use[0][0]=use[1][0],use[0][5]=use[1][5];
    dfs(poi+1,num+plus+1,1);
    use[0][0]=t1,use[0][5]=t2;

    // bian huan bian huan chuan
    if(use[0][5]!=use[1][5])
    {
    plus=abs(use[1][0]-use[0][0])+1+abs(use[1][5]-use[0][5])+1;
    use[0][0]=use[1][0],use[0][5]=use[1][5];
    dfs(poi+1,num+plus+1,1);
    use[0][0]=t1,use[0][5]=t2;

    }

    return ;
    }

    t1=use[0][poi];

    plus=abs(use[0][poi]-use[1][poi]);
    use[0][poi]=use[1][poi];
    dfs(poi+1,num+plus+1,yi);
    use[0][poi]=t1;

    t2=use[0][0];
    plus=abs(use[0][0]-use[1][poi])+1;
    use[0][0]=use[0][poi],use[0][poi]=use[1][poi];
    dfs(poi+1,num+plus+1,yi);
    use[0][0]=t2,use[0][poi]=t1;

    t2=use[0][0];
    plus=abs(use[0][poi]-use[1][0])+1+abs(use[1][poi]-use[0][0]);
    use[0][poi]=use[1][poi],use[0][0]=use[1][0];
    dfs(poi+1,num+plus+1,1);
    use[0][0]=t2;use[0][poi]=t1;

    t2=use[0][0],t3=use[0][5];
    s0(poi),s1(poi);
    plus=2+abs(use[0][poi]-use[1][poi]);
    use[0][poi]=use[1][poi];
    dfs(poi+1,num+plus+1,yi);
    use[0][0]=t2,use[0][5]=t3,use[0][poi]=t1;

    s1(poi),s0(poi);
    plus=2+abs(use[0][poi]-use[1][poi]);
    use[0][poi]=use[1][poi];
    dfs(poi+1,num+plus+1,yi);
    use[0][0]=t2,use[0][5]=t3,use[0][poi]=t1;

    s0(poi),s1(poi);
    plus=2+abs(use[0][poi]-use[1][poi])+abs(t1-use[1][0]);
    use[0][poi]=use[1][poi];use[0][0]=use[1][0];
    dfs(poi+1,num+plus+1,yi);
    use[0][0]=t2,use[0][5]=t3,use[0][poi]=t1;

    s1(poi),s0(poi);
    plus=2+abs(use[0][poi]-use[1][poi])+abs(t3-use[1][0]);
    use[0][poi]=use[1][poi];use[0][0]=use[1][0];
    dfs(poi+1,num+plus+1,yi);
    use[0][0]=t2,use[0][5]=t3,use[0][poi]=t1;

    t2=use[0][5];
    plus=abs(use[0][5]-use[1][poi])+1;
    use[0][5]=use[0][poi],use[0][poi]=use[1][poi];
    dfs(poi+1,num+plus+1,yi);
    use[0][poi]=t1,use[0][5]=t2;

    t2=use[0][5];
    plus=abs(use[0][poi]-use[1][5])+1+abs(use[1][poi]-use[0][5]);
    use[0][poi]=use[1][poi],use[0][5]=use[1][5];
    dfs(poi+1,num+plus+1,1);
    use[0][5]=t2;use[0][poi]=t1;

    }

    void into()
    {
    string s;
    for(int i=0;i<2;i++)
    {
    cin>>s;
    for(int j=0;j<6;j++)
    {
    use[i][j]=s[j]-'0';
    if((cnt[use[i][j]]==0)&&(i==1))
    one[++one[0]]=use[i][j],cnt[use[i][j]]++;
    }
    }
    }

    int main()
    {
    into();
    now=0;

    if(check())ans=0;
    else dfs(0,0,0);

    printf("%d",ans);

    //while(1);
    return 0;
    }

  • 0
    @ 2016-01-02 08:06:44

    一开始还打了好多行...后来发现用一个数组s记下head里的序列,对它进行操作可以使代码简洁

  • 0
    @ 2016-01-02 08:03:34

    不加任何剪枝的裸BFS也可以90分...不过大部分是卡着时限过的

  • 0
    @ 2016-01-02 08:02:20

    只要一个剪枝就可以快速过:2~5位置上没达到目标状态不要用左右移

    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    using namespace std;
    bool hash[10][10][10][10][10][10][7]; //序列为(a,b,c,d,e,f)且光标在g的状态是否出现过
    struct bfs
    {
    char a[7];
    char pos;
    int dep;
    }q[1000001]; //存下数字与光标位置

    int h=0,t=1;
    char ait[7];
    int p,d;
    char s[7];

    bool check(char a,char b,char c,char d,char e,char f,int g)
    {
    return hash[a-'0'][b-'0'][c-'0'][d-'0'][e-'0'][f-'0'][g];
    }

    bool yes(int k)
    {
    int i;
    for(i=1;i<=6;i++)
    if(q[k].a[i]!=ait[i]) return 0;
    return 1;
    }

    void change(char a,char b,char c,char d,char e,char f,int g)
    {
    hash[a-'0'][b-'0'][c-'0'][d-'0'][e-'0'][f-'0'][g]=1;
    }

    void mcheck( )
    {
    int i;
    if(!check(s[1],s[2],s[3],s[4],s[5],s[6],p))
    {
    change(s[1],s[2],s[3],s[4],s[5],s[6],p);
    t=(t+1)%1000000;
    for(i=1;i<=6;i++)
    q[t].a[i]=s[i];
    q[t].pos=p;
    q[t].dep=d+1;
    if(yes(t)) {printf("%d",d+1);exit(0);}
    }
    }

    int main( )
    {

    int i,j,temp;
    char c;

    for(i=1;i<=6;i++)
    scanf("%c",&q[1].a[i]);

    scanf(" ");

    for(i=1;i<=6;i++)
    scanf("%c",&ait[i]);

    q[1].pos=1;
    q[1].dep=0;

    //有一个点初始状态就是要求状态...
    for(i=1;i<=6;i++)
    if(ait[i]!=q[1].a[i]) goto trys;

    printf("0");return 0;

    trys:;
    while(h!=t)
    {
    h=(h+1)%1000000;
    p=q[h].pos;
    d=q[h].dep;
    for(i=1;i<=6;i++)
    s[i]=q[h].a[i];

    if(p!=1)
    {
    temp=s[p];s[p]=s[1];s[1]=temp;
    mcheck( );
    temp=s[p];s[p]=s[1];s[1]=temp;
    }

    if(p!=6)
    {
    temp=s[p];s[p]=s[6];s[6]=temp;
    mcheck( );
    temp=s[p];s[p]=s[6];s[6]=temp;
    }

    if(s[p]!='0')
    {
    s[p]--;
    mcheck( );
    s[p]++;
    }

    if(s[p]!='9')
    {
    s[p]++;
    mcheck( );
    s[p]--;
    }

    if(p==1 || p==6 || s[p]==ait[p]) //如果目前光标在2~5且当前位置上不符合要求,那么左移和右移不可能使其符合要求
    {
    if(p!=1)
    {
    p--;
    mcheck( );
    p++;
    }

    if(p!=6)
    {
    p++;
    mcheck( );
    }
    }
    }

    return 0;
    }

  • 0
    @ 2015-12-09 17:40:43

    测试数据 #0: Accepted, time = 93 ms, mem = 12172 KiB, score = 10

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

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

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

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

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

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

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

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

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

    作为一个傻逼。。。
    人家100行代码我写了280+。。。。
    算了贴个代码c++的
    #include<bits/stdc++.h>
    using namespace std;
    class bitell
    {
    public:
    int a[7];
    // int w;
    int light;
    bitell();
    bitell swap1();
    bitell swap0();
    bitell left();
    bitell right();
    bitell up();
    bitell down();
    bitell copyer();
    };
    void shuchu(bitell);
    bitell::bitell()
    {
    light=1;
    }
    inline bitell bitell::copyer()
    {
    bitell p;
    p.light=light;
    for(int i=1;i<=6;i++)
    p.a[i]=a[i];
    return p;
    }
    inline bitell bitell::swap0()
    {
    int swapl;
    bitell p;
    p=copyer();
    swapl=p.a[light];
    p.a[light]=p.a[1];
    p.a[1]=swapl;
    return p;
    }
    inline bitell bitell::swap1()
    {
    bitell p;
    int swapl;
    p=copyer();
    swapl=p.a[light];
    p.a[light]=p.a[6];
    p.a[6]=swapl;
    return p;
    }
    inline bitell bitell::up()
    {
    bitell p;
    p=copyer();
    if(p.a[light]!=9)
    p.a[light]++;
    return p;
    }
    inline bitell bitell::down()
    {
    bitell p;
    p=copyer();
    if(p.a[light]!=0)
    p.a[light]--;
    return p;
    }
    inline bitell bitell::left()
    {
    bitell p;
    p=copyer();
    if(p.light!=1)
    p.light--;
    return p;
    }
    inline bitell bitell::right()
    {
    bitell p;
    p=copyer();
    if(p.light!=6)
    p.light++;
    return p;
    }
    queue<bitell> q;
    queue<bitell> p;
    bool vis[6000000];
    bool vis2[6000000];
    bitell start,fll;
    int minl=-1;
    int plength=1,qlength=1;
    inline int change(bitell w)
    {
    int l=((w.a[1])*100000+(w.a[2])*10000+(w.a[3])*1000+(w.a[4])*100+(w.a[5])*10+(w.a[6]))+(w.light-1)*1000000;
    return l;
    }
    bool operator ==(bitell a,bitell b)
    {
    for(int i=1;i<=6;i++)
    if(a.a[i]!=b.a[i])
    return false;
    return true;
    }
    inline void put(bitell w)
    {
    if(vis[change(w)])
    return;
    if(w.a[w.light]!=0)
    {
    qlength++;
    q.push(w.down());
    }
    if(w.light!=1&&((w.light==1||w.light==6)||(w.a[w.light]==fll.a[w.light])))
    {
    qlength++;
    q.push(w.left());
    }
    if(w.light!=6&&((w.light==1||w.light==6)||(w.a[w.light]==fll.a[w.light])))
    {
    qlength++;
    q.push(w.right());
    }
    if(w.a[w.light]!=w.a[1])
    {
    qlength++;
    q.push(w.swap0());
    }
    if(w.a[w.light]!=9)
    {
    qlength++;
    q.push(w.up());
    }
    if(w.a[w.light]!=w.a[6])
    {
    qlength++;
    q.push(w.swap1());
    }
    return;
    }
    inline void put2(bitell w)
    {
    if(vis2[change(w)])
    return;
    if(w.a[w.light]!=0)
    {
    plength++;
    p.push(w.down());
    }
    if(w.light!=1&&((w.light==1||w.light==6)||(w.a[w.light]==start.a[w.light])))
    {
    plength++;
    p.push(w.left());
    }
    if(w.light!=6&&((w.light==1||w.light==6)||(w.a[w.light]==start.a[w.light])))
    {
    plength++;
    p.push(w.right());
    }
    if(w.a[w.light]!=w.a[1])
    {
    plength++;
    p.push(w.swap0());
    }
    if(w.a[w.light]!=9)
    {
    plength++;
    p.push(w.up());
    }
    if(w.a[w.light]!=w.a[6])
    {
    plength++;
    p.push(w.swap1());
    }
    return;
    }

    bool find(int k)
    {
    int p1=qlength;
    int oo;
    while(p1!=0)
    {
    oo=change(q.front());
    if(vis2[oo]||q.front()==fll)
    {
    minl=k;
    return 1;
    }
    put(q.front());
    vis[oo]=true;
    q.pop();
    p1--;
    qlength--;
    }
    return 0;
    }
    bool find2(int k)
    {
    int p1=plength;
    int oo;
    while(p1!=0)
    {
    oo=change(p.front());
    if(vis[oo]||p.front()==start)
    {
    minl=k;
    return 1;
    }
    put2(p.front());
    vis2[oo]=true;
    p.pop();
    plength--;
    p1--;
    }
    return 0;
    }
    void clean()
    {
    while(!q.empty())
    q.pop();
    while(!p.empty())
    p.pop();
    return;
    }
    int main()
    {
    bool flag=1;
    int kk=0;
    minl=99999;
    char pl[7];
    for(int i=1;i<=6;i++)
    cin>>pl[i];
    for(int i=1;i<=6;i++)
    start.a[i]=pl[i]-'0';
    for(int i=1;i<=6;i++)
    cin>>pl[i];
    for(int i=1;i<=6;i++)
    fll.a[i]=pl[i]-'0';
    if(fll==start)
    {
    cout<<0<<endl;
    return 0;
    }
    for(int i=1;i<=6;i++)
    {
    memset(vis,false,sizeof(vis));
    memset(vis2,false,sizeof(vis2));
    clean();
    q.push(start);
    p.push(fll);
    find(0);
    find2(0);
    kk=1;
    while(1)
    {
    if(qlength>plength)
    {
    if(find2(kk))
    break;
    }
    else
    if(find(kk))
    break;
    kk++;
    if(qlength>plength)
    {
    if(find2(kk))
    break;
    }
    else
    if(find(kk))
    break;
    kk++;
    if(kk>=minl)
    break;
    }
    ww:
    plength=qlength=1;
    fll.light++;
    }
    cout<<minl<<endl;
    return 0;
    }

  • 0
    @ 2014-07-02 19:12:44

    program p1673;
    var
    f:array[0..720,1..6,1..2] of byte;
    ans:array[0..720,1..6] of byte;
    que:array[0..8000] of string;
    que2:array[0..8000] of byte;
    i,j:longint;
    min:integer;
    search:integer;
    inp,aim,t:string;
    procedure dfs;
    var
    p1,p2:integer;
    work2:char;
    link,tail:integer;
    function hash(n:string):integer;
    var
    jc2:integer;
    i,j,k:longint;
    f:array[1..6] of byte;
    len:integer;
    begin
    for i:=1 to 6 do begin f[i]:=i; end;
    jc2:=120; len:=length(N);
    hash:=0;
    for i:=6 downto 2 do begin
    val(n[len-i+1],j);
    hash:=hash+(f[j]-1)*jc2;
    for k:=j+1 to 6 do begin
    f[k]:=f[k]-1; end;
    jc2:=jc2 div (i-1);
    end;
    end;
    procedure count(a,b:integer);
    var
    i,j,k,l:longint;
    x:integer;
    compare:string;
    begin
    x:=0;
    compare:='';
    k:=0;
    for i:=1 to 6 do begin
    val(que[link][i],j);
    compare:=compare+t[j];
    end;
    for i:=1 to 6 do begin
    val(aim[i],j);
    val(compare[i],l);
    x:=x+abs(j-l);end;
    if compare[6]<>aim[6] then k:=6;
    if compare[5]<>aim[5] then k:=k+4
    else if compare[4]<>aim[4] then k:=k+3
    else if compare[3]<>aim[3] then k:=k+2
    else if compare[2]<>aim[2] then k:=k+1;
    if f[a,b,2]=5 then f[a,b,2]:=10;
    if f[a,b,2]=10 then ans[a,b]:=x+f[a,b,1]
    else if (f[a,b,2]>5) then begin
    if (k>5) then begin if (f[a,b,2]>=k) then ans[a,b]:=x+f[a,b,1];end
    else if (f[a,b,2]-6>=k) then ans[a,b]:=x+f[a,b,1]; end
    else if f[a,b,2]>=k then ans[a,b]:=x+f[a,b,1];
    end;
    begin
    link:=0;
    tail:=1;
    f[0,1,1]:=0;
    f[0,1,2]:=0;
    que[0]:='123456';
    que2[0]:=1;
    while search>0 do begin
    //swap 0
    if que2[link]>1 then begin
    p1:=hash(que[link]);
    work2:=que[link][que2[link]];
    que[link][que2[link]]:=que[link][1];
    que[link][1]:=work2;
    p2:=hash(que[link]);
    if f[p2,que2[link],1]=200 then begin
    f[p2,que2[link],2]:=f[p1,que2[link],2];
    f[p2,que2[link],1]:=f[p1,que2[link],1]+1;
    count(p2,que2[link]);
    search:=search-1;
    que2[tail]:=que2[link];
    que[tail]:=que[link];
    tail:=tail+1;
    if tail>8000 then tail:=1;
    end;
    work2:=que[link][que2[link]];
    que[link][que2[link]]:=que[link][1];
    que[link][1]:=work2;
    end;
    //swap 6
    if que2[link]<6 then begin
    p1:=hash(que[link]);
    work2:=que[link][que2[link]];
    que[link][que2[link]]:=que[link][6];
    que[link][6]:=work2;
    p2:=hash(que[link]);
    if f[p2,que2[link],1]=200 then begin
    f[p2,que2[link],1]:=f[p1,que2[link],1]+1;
    if f[p1,que2[link],2]<5 then begin
    f[p2,que2[link],2]:=f[p1,que2[link],2]+6;
    end else f[p2,que2[link],2]:=f[p1,que2[link],2];
    count(p2,que2[link]);
    search:=search-1;
    que2[tail]:=que2[link];
    que[tail]:=que[link];
    tail:=tail+1;
    if tail>8000 then tail:=1;
    end;
    work2:=que[link][que2[link]];
    que[link][que2[link]]:=que[link][6];
    que[link][6]:=work2;
    end;
    //left
    if que2[link]>1 then begin
    p1:=hash(que[link]);
    que2[link]:=que2[link]-1;
    if f[p1,que2[link],1]=200 then begin
    f[p2,que2[link],2]:=f[p1,que2[link],2];
    f[p1,que2[link],1]:=f[p1,que2[link]+1,1]+1;
    search:=search-1;
    count(p1,que2[link]);
    que2[tail]:=que2[link];
    que[tail]:=que[link];
    tail:=tail+1;
    if tail>8000 then tail:=1; end;
    que2[link]:=que2[link]+1;

    end;

    //right
    if que2[link]<6 then begin
    p1:=hash(que[link]);
    que2[link]:=que2[link]+1;
    if f[p1,que2[link],1]=200 then begin
    f[p1,que2[link],1]:=f[p1,que2[link]-1,1]+1;
    if (f[p1,que2[link]-1,2]<>10) then begin
    if f[p1,que2[link]-1,2]>5 then begin if ((f[p1,que2[link]-1,2]-5)=que2[link]-1) then f[p1,que2[link],2]:=f[p1,que2[link]-1,2]+1; end

    else if (f[p1,que2[link]-1,2]+2=que2[link]) then f[p1,que2[link],2]:=f[p1,que2[link]-1,2]+1;
    end
    else f[p1,que2[link],2]:=10;
    search:=search-1;
    count(p1,que2[link]);
    que2[tail]:=que2[link];
    que[tail]:=que[link];
    tail:=tail+1; if tail>8000 then tail:=1; end;que2[link]:=que2[link]+1;

    end;

    link:=link+1;
    if link>8000 then search:=0;

    end;
    end; // all procedure
    begin //main
    read(inp);
    fillchar(ans,sizeof(ans),100);
    for i:=0 to 720 do
    for j:=1 to 6 do begin
    f[i,j,1]:=200;
    f[i,j,2]:=0;end;
    t:=copy(inp,1,6);
    aim:=copy(inp,8,6);
    min:=201;
    search:=720*6;
    if t=aim then min:=0
    else dfs;
    for i:=0 to 719 do
    for j:=1 to 6 do begin
    if ans[i,j]<min then min:=ans[i,j];
    end;
    writeln(min);
    end.
    看了大神的题解之后弄了一星期终于过了。。。

  • 0
    @ 2014-06-21 12:57:54

    内存1000000*6的byte就OK。。然后弱菜依然TLE。。。。55555~

  • 0
    @ 2012-09-06 18:34:57

    编译通过...

    ├ 测试数据 01:答案正确... (311ms, 84648KB)

    ├ 测试数据 02:答案正确... (690ms, 84648KB)

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

    ├ 测试数据 04:答案正确... (831ms, 84648KB)

    ├ 测试数据 05:答案正确... (128ms, 84648KB)

    ├ 测试数据 06:答案正确... (815ms, 84648KB)

    ├ 测试数据 07:答案正确... (659ms, 84648KB)

    ├ 测试数据 08:答案正确... (784ms, 84648KB)

    ├ 测试数据 09:答案正确... (675ms, 84648KB)

    ├ 测试数据 10:答案正确... (522ms, 84648KB)

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

    Accepted / 100 / 5418ms / 84648KB

    最朴素的宽搜..... 缩小内存用 byte

  • 0
    @ 2010-03-29 19:33:31

    内存挂了……我顶……看来这道题真的很不简单

  • 0
    @ 2009-11-02 08:37:57

    1秒..........................

    我去改改原来的程序.............

  • 0
    @ 2009-10-30 14:22:03

    额,时限这么短,看来单纯的宽搜是不行了。难道是双向宽搜或A*?

    膜拜过了的神牛们!

  • 0
    @ 2009-10-24 12:15:44

    555..TLE and MLE

  • 0
    @ 2009-10-23 17:57:52

    TLE..

  • 0
    @ 2009-10-22 22:25:39

    现在很流行留名?

  • 0
    @ 2009-10-22 11:39:19

    当年的竞赛不是时限到了好几秒吗...本人小菜...时限短了过不了...

  • 0
    @ 2009-10-21 21:49:33

    看到zbwmqlw破了处来这里鄙视完zbwmqlw走人

信息

ID
1673
难度
7
分类
搜索 点击显示
标签
递交数
581
已通过
90
通过率
15%
被复制
3
上传者