solution.md

# 跳蚱蜢

有 9 只盘子，排成 1 个圆圈。

其中 8 只盘子内装着 8 只蚱蜢，有一个是空盘，我们把这些蚱蜢顺时针编号为 1 ~ 8

每只蚱蜢都可以跳到相邻的空盘中，也可以再用点力，越过一个相邻的蚱蜢跳到空盘中。

请你计算一下，如果要使得蚱蜢们的队形改为按照逆时针排列，

并且保持空盘的位置不变（也就是 1-8 换位，2-7 换位,…），至少要经过多少次跳跃？

![](https://img-blog.csdnimg.cn/20200530104930106.png)

以下选项<span style="color:red">错误</span>的是？

## aop

### before

```c
#include <bits/stdc++.h>
using namespace std;
```

### after

```c

```

## 答案

```c
const int MAXN = 1e7;

int arr[9] = {4, 3, 2, 1, 0, 8, 7, 6, 5};

int tar[9] = {5, 6, 7, 8, 0, 1, 2, 3, 4};

int que[MAXN][9];

int dist[MAXN];

int pos[MAXN];

struct cmp
{
    bool operator()(int a, int b)
    {
        return memcmp(que[a], que[b], sizeof(int) * 9) < 0;
    }
};

set<int, cmp> vis;

void set_init()
{
    vis.clear();
}

bool inset_check(int a)
{
    if (vis.find(a) == vis.end())
    {
        vis.insert(a);
        return true;
    }
    return false;
}

int bfs()
{

    int front = 1;
    int rear = 2;
    pos[front] = 4;
    dist[front] = 0;
    memcpy(que[front], arr, sizeof(int) * 9);

    while (front < rear)
    {
        int *a = que[front];

        if (memcmp(a, tar, sizeof(int) * 9) == 0)
            return front;

        for (int i = -2; i <= 2; i++)
        {
            if (i == 0)
                continue;

            int new_pos = (pos[front] + i + 9) % 9;
            int *t = que[rear];
            memcpy(t, a, sizeof(int) * 9);
            dist[rear] = dist[front];

            t[new_pos] = a[pos[front]];
            t[pos[front]] = a[new_pos];
            pos[rear] = new_pos;

            if (inset_check(rear))
                rear++;
        }
        front++;
    }
    return 0;
}

int main()
{
    int ans = bfs();
    printf("%d\n", dist[ans]);

    return 0;
}
```

## 选项

### A

```c
string start = "012345678";
string e = "087654321";
int main()
{
    queue<pair<string, int>> q;
    q.push(make_pair(start, 0));
    set<string> s;
    s.insert(start);
    while (!q.empty())
    {
        string a = q.front().first;
        int level = q.front().second;
        if (a == e)
        {
            cout << level;
            break;
        }
        q.pop();
        int pos = 0;
        while (a[pos] != '0')
            pos++;
        int posi[4];
        posi[0] = (pos + 8) % 9;
        posi[1] = (pos + 1) % 9;
        posi[2] = (pos + 7) % 9;
        posi[3] = (pos + 2) % 9;
        for (int i = 0; i < 4; i++)
        {
            string b = a;
            b[pos] = b[posi[i]];
            b[posi[i]] = '0';
            if (s.count(b) == 0)
            {
                s.insert(b);
                q.push(make_pair(b, level + 1));
            }
        }
    }
    return 0;
}
```

### B

```c
struct node
{
    string str;
    int pos;
    int step;
    node(string str, int pos, int step) : str(str), pos(pos), step(step) {}
};
int N = 9;
set<string> visited;
queue<node> q;
void insertq(node no, int i)
{
    string s = no.str;
    swap(s[no.pos], s[(no.pos + i + 9) % 9]);

    if (visited.count(s) == 0)
    {
        visited.insert(s);
        node n(s, (no.pos + i + 9) % 9, no.step + 1);
        q.push(n);
    }
}
int main()
{
    node first("012345678", 0, 0);
    q.push(first);

    while (!q.empty())
    {
        node temp = q.front();
        if (temp.str == "087654321")
        {
            cout << temp.step;
            break;
        }
        else
        {

            insertq(temp, 1);
            insertq(temp, -1);
            insertq(temp, 2);
            insertq(temp, -2);
            q.pop();
        }
    }
}
```

### C

```c
int dir[] = {1, -1, 2, -2};
unordered_map<string, int> dist;
string S = "12345678X", T = "87654321X";

int bfs()
{
    queue<string> q;
    q.push(S);
    dist[S] = 0;

    while (q.size())
    {
        string t = q.front();
        q.pop();

        if (t == T)
            return dist[t];

        int k = t.find('X'), distance = dist[t];
        for (int i = 0; i < 4; i++)
        {
            swap(t[k], t[(k + dir[i] + 9) % 9]);
            if (!dist.count(t))
            {
                q.push(t);
                dist[t] = distance + 1;
            }
            swap(t[k], t[(k + dir[i] + 9) % 9]);
        }
    }

    return -1;
}

int main()
{
    cout << bfs() << endl;
    return 0;
}
```