C++14(g++5.4) 解法, 执行用时: 14ms, 内存消耗: 4708K, 提交时间: 2019-11-07 17:57:25

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


int toInt(vector<string> &M) {
  int tot = 0;
  for (auto &s: M) {
    for (auto ch: s) tot = tot * 2 + ch - '0';
  }
  return tot;
}
vector<string> toGrid(int n) {
  vector<string> G(4, "0000");
  for (int i = 3; i >= 0; i--) {
    for (int j = 3; j >= 0; j--) {
      G[i][j] = n%2 + '0';
      n /= 2;
    }
  }
  return G;
}
int step[1<<20];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

int main() {
  memset(step, 0x3f, sizeof(step));
  vector<string> from(4); for (auto &s: from) cin >> s;
  vector<string> to(4); for (auto &s: to) cin >> s;
  // for (auto s: from) cout << s << endl;
  // for (auto s: to) cout << s << endl;

  auto s = toInt(from);
  queue<int> Q; Q.push(s);
  step[s] = 0;
  while (!Q.empty()) {
    auto s = Q.front(); Q.pop();
    auto g = toGrid(s); 
    //  cout << "Pop" << endl;
  //  for (auto s: g) cout << s << endl;
    for (int x = 0; x < 4; x++) {
      for (int y = 0; y < 4; y++) if (g[x][y] == '1') {
        for (int i = 0; i < 4; i++) {
          int nx = x + dx[i]; 
          int ny = y + dy[i];
          if (0 <= nx && nx < 4 && 0 <= ny && ny < 4 && g[nx][ny] != '1') {
            swap(g[x][y], g[nx][ny]);
            int t = toInt(g);
            if (step[t] == 0x3f3f3f3f) {
              step[t] = step[s] + 1;
  //   cout << "Push" << endl;
  //  for (auto s: g) cout << s << endl;
              Q.push(t);
            }
            swap(g[x][y], g[nx][ny]);
          }
        }
      }
    }
  }
  cout << step[toInt(to)] << endl;
  
}

C++(g++ 7.5.0) 解法, 执行用时: 46ms, 内存消耗: 1820K, 提交时间: 2022-09-23 20:08:48

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
typedef pair<int,int>PII;
typedef long long ll;
string st ,ed;
map<string,int>dist;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int bfs()
{
    queue<string >q;
    q.push(st);
    dist[st]=0;
    while(q.size())
    {
        string t=q.front();
        string p;
        q.pop();
        for(int i=0;i<16;i++)
            if(t[i]=='1')
            for(int j=0;j<4;j++)
        {
            p=t;
            int x=i/4+dx[j];
            int y=i%4+dy[j];
            if(x<0||x>3||y<0||y>3||p[i]==p[4*x+y])continue;
            swap(p[i],p[4*x+y]);
            if(dist[p]==0)
            {
                q.push(p);
                dist[p]=dist[t]+1;
            }
            if(p==ed)
                return dist[p];
        }
    }
    return 0;

}
int  main()
{
    string a;
    for(int i=1;i<=4;i++)
    {
        cin>>a;
        st+=a;
    }
    for(int i=1;i<=4;i++)
    {
        cin>>a;
        ed+=a;
    }
    if(st==ed)
        cout<<0<<endl;
    else 
    cout<<bfs()<<endl;
    return 0;
}

C++(clang++11) 解法, 执行用时: 57ms, 内存消耗: 1784K, 提交时间: 2020-12-02 00:02:19

#include<iostream>
#include<map>
#include<queue>
using namespace std;
map<string, int> ha;
queue<string> q;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int main(){
	string beg,end,a;
	for(int i=0;i<4;i++){
		cin>>a;
		beg=beg+a;
	}
	for(int i=0;i<4;i++){
		cin>>a;
		end=end+a;
	}
	q.push(beg);
	ha[beg]=0;
	if(beg==end){
		cout<<"0";
		return 0;
	}
	string p,pp;
	while(q.empty()!=1){
		p=q.front();
		int len=p.length();
		for(int i=0;i<len;i++){
			for(int j=0;j<4;j++){
				pp=p;
				int xx=i/4+dx[j];
				int yy=i%4+dy[j];
				if(xx<0||xx>3||yy<0||yy>3||pp[i]==pp[xx*4+yy])
                    continue;
                swap(pp[i], pp[xx*4+yy]);
				if(ha[pp]==0){
					q.push(pp);
					ha[pp]=ha[p]+1;
				}
				if(pp==end){
					cout<<ha[pp];
					return 0;
				}
			}
		}
		q.pop();
	}
	return 0;
}