hdu 5012 bfs --- 慎用STL 比方MAP判重

http://acm.hdu.edu.cn/showproblem.php?pid=5012

发现一个问题 假设Sting s = '1'+'2'+'3';

s!="123"!!!!!!  而是有乱码

先贴一份自己的TLE 代码，

超时应该是由于：

1、cin

2、map判重 map find太花时间

3、string花时间

4、事实上不用两个都旋转，仅仅要旋转一个即可，这样能够省下非常多时间 包含少用了make_pair pair的判重等等....哎  二笔了  太暴力了

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <iostream>

#include <set>

#include <queue>

#include <map>

using namespace std;

#define IN(s) freopen(s,"r",stdin)

#define CL(a,b) memset(a,b,sizeof(a))

map< pair<string ,string>, int>mp;

string left(string x)

{

    string tmp;

    tmp+=x[3];

    tmp+=x[2];

    tmp+=x[0];

    tmp+=x[1];

    tmp+=x[4];

    tmp+=x[5];

    //cout << "st" << tmp << endl;

    //x=tmp;

    return tmp;

}

string right(string x)

{

    string tmp;

    //tmp=x[2]+x[3]+x[1]+x[0]+x[4]+x[5];

    tmp+=x[2];

    tmp+=x[3];

    tmp+=x[1];

    tmp+=x[0];

    tmp+=x[4];

    tmp+=x[5];

    //x=tmp;

    return tmp;

}

string front(string x)

{

    string tmp;

    //tmp= x[5]+x[4]+x[2]+x[3]+x[0]+x[1];

    tmp+= x[5];

    tmp+=x[4];

    tmp+=x[2];

    tmp+=x[3];

    tmp+=x[0];

    tmp+=x[1];

    //x=tmp;

    return tmp;

}

string back(string x)

{

    string tmp;

    //tmp=x[4]+x[5]+x[2]+x[3]+x[1]+x[0];

    tmp+=x[4];

    tmp+=x[5];

    tmp+=x[2];

    tmp+=x[3];

    tmp+=x[1];

    tmp+=x[0];

    //x=tmp;

    return tmp;

}

queue< pair<string,string> >q;

string a,b;

int solve()

{

    while(!q.empty())q.pop();

    mp[ make_pair(a,b) ]=0;

    q.push( make_pair(a,b) );

    int flag=0;

    while(!q.empty())

    {

        pair <string,string> tp;

        tp.first=q.front().first;

        tp.second=q.front().second;

        if(tp.first == tp.second){flag=1; return mp[tp];}

        string tmp=left(tp.first);

        if(mp.find(make_pair(tmp,tp.second)) == mp.end()) {mp[make_pair(tmp,tp.second)]=mp[tp]+1; q.push(make_pair(tmp,tp.second)); }

        tmp=left(tp.second);if(mp.find(make_pair(tp.first,tmp))== mp.end()) { mp[make_pair(tp.first,tmp)]=mp[tp]+1;q.push(make_pair(tp.first,tmp)); }

        tmp=right(tp.first);if(mp.find(make_pair(tmp,tp.second)) == mp.end()) {mp[make_pair(tmp,tp.second)]=mp[tp]+1; q.push(make_pair(tmp,tp.second)); }

        tmp=right(tp.second);if(mp.find(make_pair(tp.first,tmp))  == mp.end()){ mp[make_pair(tp.first,tmp)]=mp[tp]+1;q.push(make_pair(tp.first,tmp)); }

        tmp=front(tp.first);if(mp.find(make_pair(tmp,tp.second)) == mp.end()) {mp[make_pair(tmp,tp.second)]=mp[tp]+1; q.push(make_pair(tmp,tp.second)); }

        tmp=front(tp.second);if(mp.find(make_pair(tp.first,tmp))  == mp.end()) { mp[make_pair(tp.first,tmp)]=mp[tp]+1;q.push(make_pair(tp.first,tmp)); }

        tmp=back(tp.first);if(mp.find(make_pair(tmp,tp.second)) == mp.end()) {mp[make_pair(tmp,tp.second)]=mp[tp]+1; q.push(make_pair(tmp,tp.second)); }

        tmp=back(tp.second);if(mp.find(make_pair(tp.first,tmp))  == mp.end()) { mp[make_pair(tp.first,tmp)]=mp[tp]+1;q.push(make_pair(tp.first,tmp)); }

        q.pop();

    }

    if(!flag)

      return -1;

}

int main()

{

    //IN("hdu5012.txt");

    while(cin>>a)

    {

        b="";//

        string tmp;

        for(int i=0;i<5;i++)

        {

            cin>>tmp;

            a+=tmp;

        }

        for(int i=0;i<6;i++)

        {

            cin>>tmp;

            b+=tmp;

        }

        printf("%d\n",solve());

    }

    return 0;

}

看了别人的代码 由于这道题的技术含量不怎么高 懒得再写了。贴别人的把

用数组取代状态，至于判重 由于仅仅有六位数，所以化为整数然后判重即可了  代码来自http://blog.csdn.net/u011345461/article/details/39275009

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

#include <algorithm>

using namespace std;

const int MAXN = 6;

struct node{

    node() {

        memset(arr, 0, sizeof(arr));

        d = 0;

    }

    int arr[MAXN], d;

}s, e;

int vis[MAXN * 200000];

int change(node a) {

    int num = 0;

    for (int i = 0; i < MAXN; i++) {

        num = num * 10 + a.arr[i];

    }

    return num;

}

bool judge(node a, node b) {

    for (int i = 0; i < MAXN; i++)

        if (a.arr[i] != b.arr[i])

            return false;

    return true;

}

node turn(node a, int i) {

    node c;

    if (i == 1) {

        c.arr[0] = a.arr[3];

        c.arr[1] = a.arr[2];

        c.arr[2] = a.arr[0];

        c.arr[3] = a.arr[1];

        c.arr[4] = a.arr[4];

        c.arr[5] = a.arr[5];

    }

    if (i == 2) {

        c.arr[0] = a.arr[2];

        c.arr[1] = a.arr[3];

        c.arr[2] = a.arr[1];

        c.arr[3] = a.arr[0];

        c.arr[4] = a.arr[4];

        c.arr[5] = a.arr[5];

    }

    if (i == 3) {

        c.arr[0] = a.arr[5];

        c.arr[1] = a.arr[4];

        c.arr[2] = a.arr[2];

        c.arr[3] = a.arr[3];

        c.arr[4] = a.arr[0];

        c.arr[5] = a.arr[1];

    }

    if (i == 4) {

        c.arr[0] = a.arr[4];

        c.arr[1] = a.arr[5];

        c.arr[2] = a.arr[2];

        c.arr[3] = a.arr[3];

        c.arr[4] = a.arr[1];

        c.arr[5] = a.arr[0];

    }

    return c;

}

int bfs() {

    memset(vis, 0, sizeof(vis));

    queue<node> q;

    q.push(s);

    node tmp;

    vis[change(s)] = 1;

    while (!q.empty()) {

        tmp = q.front();

        q.pop();

        if (judge(tmp, e)) {

            return tmp.d;

        }

        for (int i = 1; i <= 4; i++) {

            node c;

            c = turn(tmp, i);

            if (!vis[change(c)]) {

                c.d = tmp.d + 1;

                vis[change(c)] = 1;

                q.push(c);

            }

        }

    }

    return -1;

}

int main() {

    while (scanf("%d", &s.arr[0]) != EOF) {

        for (int i = 1; i < MAXN; i++)

            scanf("%d", &s.arr[i]);

        for (int i = 0; i < MAXN; i++)

            scanf("%d", &e.arr[i]);

        printf("%d\n", bfs());

    }

    return 0;

}