[//]: # 看了下最多浏览量的题解 感觉代码有点长 索性根据八数码的启发 自己写了个 如有不足敬请指正

题目描述

在一个 4×4的棋盘上有 8个黑棋和8个白棋，当且仅当两个格子有公共边，这两个格子上的棋是相邻的。移动棋子的规则是交换相邻两个棋子。给出一个初始棋盘和一个最终棋盘，请找出一个最短的移动序列使初始棋盘变为最终棋盘。

样例

1111
0000
1110
0010

1010
0101
1010
0101

dfs爆搜 遍历到答案直接返回
用字符串存储数字 把初始状态和结束状态存好
利用队列每次更新状态 若没有被遍历过 加入队列且更新次数
遍历到终态直接返回 打印结果即可

时间复杂度n^2 n为棋盘大小

C++ 代码

#include<bits/stdc++.h>
#include<iostream>
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N=100010,M=1010;
string sta,en;//初态和末态 
unordered_map<string,int> st;//既是标记数组也是次数数组 
queue<string> q;//所需队列 
int dis; // 距离变量 
int dx[]={-1,1,0,0};//偏移量 
int dy[]={0,0,-1,1};
void dfs(string sta,string en)
{
    st[sta]=0;
    q.push(sta);//初态的初始化 
    while(q.size())
    {
        string t=q.front();
        if(t==en) return ;//每次取出来后先判断一下是否是末态 是的话直接返回 

        dis=st[t];  //记录上次次数 
        q.pop();//出队 
        for(int i=0;i<16;i++)//当前状态逐个字符遍历 
        {
            if(t[i]=='1')//是1的话进行交换 
            {
                int x=i/4,y=i%4;//找到在数组中表示的下表来进行偏移交换 
                for(int j=0;j<4;j++)
                {
                    int tx=x+dx[j];
                    int ty=y+dy[j];
                    if(tx>=0&&tx<4&&ty>=0&&ty<4)//偏移下标合法 
                    {
                      int k=tx*4+ty;//找到下表在状态中的索引 
                      if(t[k]!='1')//是0的话交换  1的话交换没意义 
                      {
                        swap(t[i],t[k]);
                        if(!st[t])//判断状态是否更新过 没的话入队 更新次数 
                          {
                              st[t]=dis+1;
                              q.push(t);    
                          }
                        swap(t[i],t[k]);//换回来为下个字符准备 
                      } 

                    }
                }
            }
        }

    }
}
int main()
{
    for(int i=1;i<=4;i++)
    {
        string x;
        cin>>x;
        sta+=x;//初末态的初始化 
    }
    for(int i=1;i<=4;i++)
    {
        string x;
        cin>>x;
        en+=x;
    }
   dfs(sta,en);//调用和打印 
   cout<<st[en]<<endl;
  return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla