uva-704-暴力枚举-双向bfs

题意：俩个转盘，24个数字，每个转盘都可以顺时针,逆时针旋转.终点固定.

问:给定一个起点,能不能在16步内转到终点

解法:双向bfs,终点走8步，起点走8步,判断从起点生成的状态是否在终点里面,如果在即是有解

注意题目要输出转动的方向,并且方向字符串要最小,所以，在某一步有解事，要把当前层数走完，取最小值

#include <iostream>

#include<map>

#include<memory.h>

#include<stdio.h>

#include<string>

#include<queue>

using namespace std;

const int MAXN = ;

string zhuan(string str, int way)

{

    string reStr(str);

    if (way == )

    {

        //左边顺时针旋转

        char sb1 = str[];

        char sb2 = str[];

        for (int i = ;i >= ;i--)

            reStr[i] = reStr[i - ];

        reStr[] = sb2;

        reStr[] = sb1;

        reStr[] = reStr[];

        reStr[] = reStr[];

        reStr[] = reStr[];

    }

    else if (way == )

    {

        //左边逆时针旋转

        char sb1 = reStr[];

        char sb2 = reStr[];

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

            reStr[i] = reStr[i + ];

        reStr[] = sb2;

        reStr[] = sb1;

        reStr[] = reStr[];

        reStr[] = reStr[];

        reStr[] = reStr[];

    }

    else if (way == )

    {

        //右边顺时针旋转

        char sb1 = reStr[];

        char sb2 = reStr[];

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

            reStr[i] = reStr[i + ];

        reStr[] = sb2;

        reStr[] = sb1;

        reStr[] = reStr[];

        reStr[] = reStr[];

        reStr[] = reStr[];

    }

    else

    {

        //右边逆时针旋转

        char sb1 = reStr[];

        char sb2 = reStr[];

        for (int i = ;i >= ;i--)

            reStr[i] = reStr[i - ];

        reStr[] = sb2;

        reStr[] = sb1;

        reStr[] = reStr[];

        reStr[] = reStr[];

        reStr[] = reStr[];

    }

    return reStr;

}

class Node

{

public:

    string str;

    string step;

    int stepNum;

    bool operator < (const Node& node) const

    {

        return stepNum > node.stepNum;

    }

};

const static string endState = "034305650121078709a90121";

map<string, string> sMap;

map<string, string>eMap;

priority_queue<Node> q;

int ok = ;

string curStep = "";

string path(string es)

{

    string str = "";

    for (int i = es.size() - ; i >= ;i--)

    {

        if (es.at(i) == '') str+= "";

        else if (es.at(i) == '') str += "";

        else if (es.at(i) == '')str += "";

        else if (es.at(i) == '') str += "";

    }

    return str;

}

//

void bfsEnd()

{

    while (!q.empty())

        q.pop();

    Node n;

    n.step = "";

    n.stepNum = ;

    n.str = endState;

    q.push(n);

    eMap[endState] = "";

    while (!q.empty())

    {

        n = q.top();

        q.pop();

        if (n.stepNum == )

            break;

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

        {

            string str = zhuan(n.str, i);

            if (eMap.find(str) == eMap.end())

            {

                string sstep(n.step);

                sstep += i + '';

                Node nn;

                nn.stepNum = n.stepNum + ;

                nn.str = str;

                nn.step = sstep;

                q.push(nn);

                eMap[str] = sstep;

            }

        }

    }

}

void bfsStart(string str)

{

    while (!q.empty())

        q.pop();

    Node n;

    n.step = "";

    n.stepNum = ;

    n.str = str;

    q.push(n);

    int okStep = INT32_MAX;

    while (!q.empty())

    {

        n = q.top();

        q.pop();

        if (ok && n.stepNum != okStep)

            break;

        if (eMap.find(n.str) != eMap.end())

        {

            if (ok == )

            {

                curStep = n.step+path(eMap.find(n.str)->second);

                okStep = n.stepNum;

                ok = ;

            }

            else

            {

                string step = n.step + path(eMap.find(n.str)->second);

                //判断大小

                if (strcmp(curStep.c_str(), step.c_str()) > )

                    curStep = step;

            }

        }

        if (ok)

            continue;

        for (int i = ; i <=  && n.stepNum != ; i++)

        {

            str = zhuan(n.str,i);

            if (sMap.find(str) == sMap.end())

            {

                string sstep(n.step);

                sstep += i + '';

                Node nn;

                nn.stepNum = n.stepNum + ;

                nn.str = str;

                nn.step = sstep;

                sMap[str] = sstep;

                q.push(nn);

            }

        }

    }

}

int main()

{

    int k = ;

    cin >> k;

    eMap.clear();

    bfsEnd();

    while (k--)

    {

        ok = ;

        sMap.clear();

        string str = "";

        int j;

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

        {

            cin >> j;

            if (j == )

                str += 'a';

            else

                str += j + '';

        }

        if (str == endState)

        {

            cout << "PUZZLE ALREADY SOLVED" << endl;

            continue;

        }

        bfsStart(str);

        if (ok==)

        {

            cout << "NO SOLUTION WAS FOUND IN 16 STEPS" << endl;

            continue;

        }

        cout << curStep << endl;

    }

}