信息学奥赛一本通T1453-移动玩具（广度搜索）

解题思路:

注意事项:

参考代码:

#include<iostream>

#include<cmath>

#include<algorithm>

#include<queue>

using namespace std;

int pre[6][6],tar[6][6],vis[65539];

int f[65539];

int dec1, dec2;

//pre初始，tar目标，vis标记1/0

//f保存每个状态的前一个状态

//dec1表示初始状态转化的十进制数

//dec2表示目标状态转换的十进制数

queue<int> q;

int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};//上下左右走路

int two_ten(int a[6][6]) //根据a数组，将玩具摆放的状态转化为十进制数。

{

    int res = 0;

    for (int i = 4; i >= 1; --i)

        for (int j = 4; j >= 1; --j)

            res += a[i][j] * pow(2, 16 - (i - 1) * 4 - j);

    return res;

}

void ten_two(int x, int a[6][6])//十进制x转化成二进制，回到数组a

{

    while (x) 

    {

        for (int i = 4; i >= 1; --i)

            for (int j = 4; j >= 1; --j)

            {

                a[i][j] = x % 2;

                x /= 2;

            }

    }

}

int judge(int x0, int y0, int xx, int yy) //判断边界内且与当前位置的值不同

{

    return (xx >= 1)&&(xx <= 4)&&(yy >= 1)&&(yy <= 4)&&(pre[x0][y0]!=pre[xx][yy]);

}

void bfs() 

{

    q.push(dec1);

    vis[dec1] = 1;

    while (!q.empty()) {

        int now = q.front();

        ten_two(now, pre);

        q.pop();

        for (int i = 1; i <= 4; ++i)

        {

            for (int j = 1; j <= 4; ++j) 

            {

                int x0 = i, y0 = j;

                for (int k = 0; k < 4; ++k) 

                {

                    int xx = x0 + dx[k], yy = y0 + dy[k], flag = 0;

                    if (judge(x0, y0, xx, yy)) 

                    {

                        flag = 1;

                        int tmpdec1 = two_ten(pre);

                        swap(pre[x0][y0], pre[xx][yy]);

                        int tmpdec2 = two_ten(pre);

                        if (!vis[tmpdec2]) 

                        {

                            vis[tmpdec2] = 1;

                            f[tmpdec2] = tmpdec1;

                            q.push(tmpdec2);

                        }

                        if (tmpdec2 == dec2) return;

                    }

                    if (flag)

                        swap(pre[x0][y0], pre[xx][yy]);

                }

           }

        }

    }

}

int main() {

    for (int i = 1; i <= 4; ++i)

        for (int j = 1; j <= 4; ++j)

            scanf("%1d", &pre[i][j]);//队列的push等等，需要用scanf的

    for (int i = 1; i <= 4; ++i)

        for (int j = 1; j <= 4; ++j)

            scanf("%1d", &tar[i][j]);

    dec1 = two_ten(pre), dec2 = two_ten(tar);

    bfs();

    if (f[dec2] == 0) cout<<-1;

    else {

        int ans = 0;

        while (f[dec2]) ans++, dec2 = f[dec2];

        printf("%d", ans);

    }

    return 0;

}