非常神奇地TLE#9

代码是预处理连边再dfs

#include <bits/stdc++.h>

using namespace std;

const int maxn = (1 << 16) + 5;

int beg, endn, cnt;
vector <int> pic[maxn];
int fa[maxn], f[maxn];
int way[maxn];
int vis[maxn];
queue <int> que;
int a[maxn], b[maxn], c[maxn], d[maxn];

bool check(int x)
{
	int cnt = 0;
	for(int i = 15; i >= 0; i --)
		if((x >> i) & 1) cnt ++;
	return (cnt == 8);
}

void bfs()
{
	que.push(beg);
	memset(f, 114, sizeof f);
    f[beg] = 0;
	while(!que.empty())
	{
		int in = que.front();
        //cout<<fa[in]<<endl;
		que.pop();
		if(vis[in])
			continue;
        vis[in] = 1;
		for(int i = 0; i < pic[in].size(); i ++)
			if(f[in] + 1 < f[pic[in][i]])
				f[pic[in][i]] = f[in] + 1, fa[pic[in][i]] = in, que.push(pic[in][i]);
	}
}

int main()
{
	for(int i = 15; i >= 0; i --)
	{
		char inp;
		cin>>inp;
		int bit = inp -'0';
		beg += bit << i;
	}
	for(int i = 15; i >= 0; i --)
	{
		char inp;
		cin>>inp;
		int bit = inp -'0';
		endn += bit << i;
	}
	for(int i = 0; i < (1 << 16); i ++)
	{
		if(!check(i))
			continue;
		int x = i;
		for(int j = 15; j >= 0; j --)
		{
			if(j >= 4 && ((x >> j) & 1) == 0 && ((x >> (j - 4)) & 1) == 1)
				pic[x].push_back(x + (1 << j) - (1 << (j - 4))), pic[x + (1 << j) - (1 << (j - 4))].push_back(x);
			else if(j >= 4 && ((x >> j) & 1) == 1 && ((x >> (j - 4)) & 1) == 0)
				pic[x].push_back(x - (1 << j) + (1 << (j - 4))), pic[x - (1 << j) + (1 << (j - 4))].push_back(x);
			if(j % 4 && ((x >> j) & 1) == 1 && ((x >> (j - 1)) & 1) == 0)
				pic[x].push_back(x - (1 << j) + (1 << (j - 1))), pic[x - (1 << j) + (1 << (j - 1))].push_back(x);
			else if(j % 4 && ((x >> j) & 1) == 0 && ((x >> (j - 1)) & 1) == 1)
				pic[x].push_back(x + (1 << j) - (1 << (j - 1))), pic[x + (1 << j) - (1 << (j - 1))].push_back(x);
		}
	}
	bfs();
	cout<<f[endn]<<endl;
	int in = endn;
	while(in != beg)
	{
		int val = (in ^ fa[in]);
		cnt ++;
		for(int i = 0; i < 16; i ++)
			if((val >> i) & 1)
			{
				if(!a[cnt])
				{
					b[cnt] = (16 - i - 1) % 4 + 1;
					a[cnt] = (16 - i - 1) / 4 + 1;
				}
				else 
				{
					d[cnt] = (16 - i - 1) % 4 + 1;
					c[cnt] = (16 - i - 1) / 4 + 1;
				}
			}
        in = fa[in];
	}
	for(int i = cnt; i >= 1; i --)
		cout<<a[i]<<b[i]<<c[i]<<d[i]<<endl;
}