HDU 1195(bfs)-蒲公英云

HDU 1195(bfs)

我就是我 2022-09-20 11:25 295阅读 0赞

题意：如题。

#include <iostream>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
bool visit[10000];
const int temp[5] = {0, 1000, 100, 10, 1};
/*
int swap(int num, int x, int y)
{
    int temp[5], i = 4;
    while (num)
    {
        temp[i--] = num % 10;
        num /= 10;
    }
    temp[x] ^= temp[y];
    temp[y] ^= temp[x];
    temp[x] ^= temp[y];
    num = 0, i = 1, x = 1000;
    while (i < 5)
    {
        num += temp[i++] * x;
        x /= 10;
    }
    return num;
}
*/
int swap(int num, int x, int y)
{
    int a = num / temp[x] % 10;
    int b = num / temp[y] % 10;
    return num - a * temp[x] - b * temp[y] + a * temp[y] + b * temp[x];
}
int _add(int num, int x)
{
    int a = num / temp[x] % 10;
    if (a == 9)
        a = -8 * temp[x];
    else a  = temp[x];
    return num + a;
}
int _minus(int num, int x)
{
    int a = num / temp[x] % 10;
    if (a == 1)
        a = 8 * temp[x];
    else a = -temp[x];
    return num + a;
}
int BFS(int start, int target)
{
    memset(visit, false, sizeof (visit));
    visit[start] = true;
    queue<int> q;
    int p, n, i, j, pre = 1, sum = 0, step = 1;
    q.push(start);
    while (!q.empty())
    {
        p = q.front(), q.pop();
        for (i = 1; i <= 4; ++i)
        {
            for (j = 0; j < 3; ++j)
            {
                if (j == 0)
                {
                    if (i == 4) continue;
                    n = swap(p, i, i + 1);
                }
                else if (j == 1)
                    n = _add(p, i);
                else n = _minus(p, i);
                if (n == target)
                    return step;
                else if (!visit[n])
                {
                    visit[n] = true;
                    q.push(n);
                    ++sum;
                }
            }
        }
        if (--pre == 0)
        {
            pre = sum;
            sum = 0;
            ++step;
        }
    }
    return -1;
}
int main()
{
    int T;
    int start, target;
    cin >> T;
    while (T--)
    {
        cin >> start >> target;
        cout << BFS(start, target) << endl;
    }
}