[Blue Bridge Cup] 2017 Preliminary Round Jumping Grasshopper

Topic description

As shown: There are 9 plates arranged in a circle. Eight of the plates contained eight grasshoppers, and one was empty.

We number these grasshoppers clockwise from 1 to 8. Each grasshopper can jump into an adjacent empty plate, or with a little more force, jump over an adjacent grasshopper into an empty plate.
Please calculate, if you want to change the formation of the grasshoppers to counterclockwise, and keep the position of the empty disk unchanged (that is, 1-8 transposition, 2-7 transposition, ...), at least how much jump?

output

output an integer representing the answer

[Summarize]
1. At first glance, I know that it is the topic of deep search, but I don't know how to record the status that has been accessed at first. The solution is to treat the sequence as a long long. Open a bool type array, the size of 1e9 is open.
2. For circular arrays, forward and backward shifts may overflow subscripts. The solution is that the coordinate formula after the transfer is
(Original coordinates + change amount + array length) % array length
ps: One thing to note is that this array must be a 0-based array.
3. About bfs. What to put in the queue, put a pair type, put the array state in the previous one, and put it away in the back.
4. When moving, after getting the changed array state after swap, you have to switch back and start another situation

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll,int> state;
bool vis[1000000000];//Arrays of bool type can be opened to such a large size, but not int
int a[12];//record array
int dx[5]={-2,-1,1,2};//Four moving directions
ll res=987654321;//result status
ll getsum()//get the number of the array state
{
    ll tem=0;
    for(int i=0;i<9;i++)
    {
        tem=tem*10+a[i];
    }
    return tem;
}

int bfs()
{
    queue<state> qu;

    qu.push(make_pair(getsum(),0));
    while(!qu.empty())
    {
        state tem=qu.front();
        qu.pop();
        ll hh=tem.first;
        //cout<<hh<<endl;
        if(hh==res)
        {

            return tem.second;
        }

        vis[hh]=true;
        int nowkg=0;
        int k=8;
        while(hh)
        {
            a[k]=hh%10;
            hh/=10;
            if(a[k]==9)
            {
                 nowkg=k;
                // cout<<k<<endl;
            }

            k--;
        }
        for(int i=0;i<4;i++)
        {
            int newkg=((nowkg+dx[i]+9)%9);
            swap(a[nowkg],a[newkg]);
            ll nowll=getsum();
            swap(a[nowkg],a[newkg]);
            if(vis[nowll]==false)
            {
                qu.push(make_pair(nowll,tem.second+1));
            }

        }

    }
}

int main()
{
    a[0]=9;
    for(int i=1;i<9;i++)
    {
        a[i]=i;
    }
    memset(vis,false,sizeof(vis));
    cout<<bfs()<<endl;
}

Tags: Algorithm

Posted by geon on Sat, 21 May 2022 05:47:10 +0300