HDU 1195 Open the Lock

1195 Open the Lock
http://acm.hdu.edu.cn/showproblem.php?pid=1195
大致题意：给你两个四位数，一个作为开始一个作为目标，有三种操作每个位可以加1可以减1，可以与相邻的交换，都算一步，求转化到目标的最小步数
#include<iostream>
#include<queue>
using namespace std;

char start[5], end[5];
int visited[10000];
struct node
{
    char str[5];
    int step;
};

void BFS()
{
    queue<node> Q;
    node q;
    strcpy(q.str, start);
    q.step = 0;
    Q.push(q);
    while (!Q.empty())
    {
        q = Q.front();
        Q.pop();
        if(strcmp(q.str, end) == 0)
        {
            cout<<q.step<<endl;
            return;
        }
        //+1
        for (int i = 0; i<4; i++)
        {
            node p = q;
            if (p.str[i] == '9') p.str[i] = '1';
            else p.str[i] += 1;
            p.step++;//加一步
            int temp;
            sscanf(p.str, "%d", &temp);
            if (!visited[temp])
            {
                visited[temp] = 1;//标记
                Q.push(p);
            }
        }
        //-1
        for (i = 0; i<4; i++)
        {
            node p = q;
            if (p.str[i] == '1') p.str[i] = '9';
            else p.str[i] -= 1;
            p.step++;//加一步
            int temp;
            sscanf(p.str, "%d", &temp);
            if (!visited[temp])
            {
                visited[temp] = 1;//标记
                Q.push(p);
            }
        }
        //exchange
        for (i = 0; i<3; i++)
        {
            node p = q;
            char t;
            t = p.str[i];
            p.str[i] = p.str[i + 1];
            p.str[i + 1] = t;
            p.step++;//加一步
            int temp;
            sscanf(p.str, "%d", &temp);
            if (!visited[temp])
            {
                visited[temp] = 1;//标记
                Q.push(p);
            }
        }
    }
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>start>>end;
        memset(visited, 0, sizeof(visited));
        BFS();
    }
    return 0;
}

补充：软件开发 , C++ ,