scy视频

#include <bits/stdc++.h>//scy教学代码（初学者用）
using namespace std;
typedef long long LL;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
struct node
{
    int a[4][4], x, y, dep, kt;//x,y表示空格的位置，dep表示当前状态是第几代的状态（与出发状态的距离），kt为状态的康托值。
};
deque<node> Q;map<LL,bool> v;

LL kt(node no)//计算状态no的康托值（把3*3的矩阵转化为一个整数），状态的判重都是用康托值
{
    LL s=0;for (int i = 1; i <= 3; i++)for (int j = 1; j <= 3; j++)s= s*10+no.a[i][j] ;
    return s;
}
int main()
{
    node stno, edno;//stno为出发状态，edno为目标状态
    for (int i = 1; i <= 3; i++)for (int j = 1; j <= 3; j++)
    {
        scanf("%d", &stno.a[i][j]);
        if (stno.a[i][j] == 0)stno.x = i, stno.y = j;
    }
    stno.dep = 0;
    stno.kt = kt(stno);

    for (int i = 1; i <= 3; i++)for (int j = 1; j <= 3; j++)scanf("%d", &edno.a[i][j]);
    edno.kt = kt(edno);

    v.clear();v[stno.kt]=1;
    Q.clear();Q.push_back(stno);
    bool bk = 0;
    while (!Q.empty())
    {
        for (int i = 0; i <= 3; i++)
        {
            node no=Q.front();
            int xx = no.x + dx[i], yy = no.y + dy[i];
            if (xx >= 1 && xx <= 3 && yy >= 1 && yy <= 3)
            {
                swap(no.a[no.x][no.y], no.a[xx][yy]);
                no.x = xx;
                no.y = yy;
                no.dep = Q.front().dep + 1;
                no.kt = kt(no);
                if (v[no.kt] == 0)
                {
                    v[no.kt] = 1;
                    Q.push_back(no);
                    if (no.kt == edno.kt){bk = 1;break;}
                }
            }
        }
        Q.pop_front();
        if (bk == 1)break;
    }
    printf("%d\n", Q.back().dep);
    return 0;
}
/*
双端队列deque<int>Q的使用 
Q.front()：返回队列头第一个元素
Q.back()：返回队列尾最后一个元素
Q.pop_front()：删除队列头第一个元素
Q.pop_back()：删除队列尾最后一个元素
Q.push_front():在队列头插入一个元素
Q.push_back():在队列尾插入一个元素
Q.empty()：判断对列是否为空
Q.size()：返回队列元素的个数
*/