思路比较简单, 搜索 + 剪枝 + 位运算, 并且每次搜索都会排除总共24 * 4种(排列+旋转)... 所以基本能瞬间完成(本地运行的话). 但是提交上去就总是超时... 求强人解答! 或者给我个容易超时的数据?

#include <iostream>
#include <fstream>
#include <bitset>
#include <vector>
using namespace std;

ifstream tin("in.txt");

int rotateTable[] = { 3, 7, 11, 15, 2, 6, 10, 14, 1, 5, 9, 13, 0, 4, 8, 12 };
int exchangeTables[24][4];
int flipTables[16][6];

void etSearch(bitset<4> used, int table[], int depth)
{
	static int etAdded = 0;
	for (int i = 0; i < 4; i++)
		if (!used[i])
		{
			bitset<4> nused = used;
			int ntable[4];
			for (int j = 0 ; j < depth; j++)
				ntable[j] = table[j];

			ntable[depth] = i;
			nused.set(i);

			if (depth < 3)
				etSearch(nused, ntable, depth + 1);
			else
			{
				int* t = exchangeTables[etAdded++];
				for (int ii = 0; ii < 4; ii++)
					t[ii] = ntable[ii];
			}
		}
}

int main()
{
	bitset<4> used;
	int table[4];
	etSearch(used, table, 0);

	for (int i = 0; i < 16; i++)
	{
		int x = i % 4;
		int y = i / 4;
		int count = 0;
		for (int iy = 0; iy < 4; iy++)
			if (iy != y)
				flipTables[i][count++] = iy * 4 + x;
		for (int ix = 0; ix < 4; ix++)
			if (ix != x)
				flipTables[i][count++] = y * 4 + ix;
	}

	unsigned short locks;

	for (int i = 0; i < 16; i++)
	{
		char status;
		tin >> status;
		if (status == '+') locks += 1;
		if (i < 15) locks <<= 1;
	}

	bool visited[0xffff];
	memset(visited, 0, sizeof visited);
	vector<unsigned short> nodes1, nodes2;
	vector<vector<int>> paths1, paths2;

	nodes1.push_back(locks);
	vector<int> spath;
	paths1.push_back(spath);

	while (true)
	{
		//cout << "size: " << nodes1.size() << endl;
		for (int i = 0; i < nodes1.size(); i++)
		{
			for (int pos = 15; pos >= 0; pos--)
			{
				unsigned short nlocks = nodes1[i];
				nlocks ^= (1 << pos);
				int* flipTable = flipTables[pos];
				for (int ii = 0; ii < 6; ii++)
					nlocks ^= (1 << flipTable[ii]);

				if (visited[nlocks]) continue;

				vector<int> npath = paths1[i];
				npath.push_back(pos);
				paths2.push_back(npath);
				nodes2.push_back(nlocks);

				if (!nlocks)
				{
					cout << npath.size() << endl;

					for (int pi = 0; pi < npath.size(); pi++)
					{
						int p = npath[pi];
						cout << (15 - p) / 4 + 1 << " " << (15 - p) % 4 + 1 << endl;
					}

					system("pause");

					return 0;
				}

				for (int eti = 0; eti < 24; eti++)
				{
					unsigned short lrlocks;
					int* et = exchangeTables[eti];

					for (int etj = 0; etj < 4; etj++)
					{
						int ls1 = etj * 4;
						int ls2 = et[etj] * 4;
						for (int etk = 0; etk < 4; etk++)
						{
							if (nlocks & (1 << (ls2 + etk)))
								lrlocks |= 1 << (ls1 + etk);
							else
								lrlocks &= ~(unsigned short)(1 << (ls1 + etk));
						}
					}
					
					visited[lrlocks] = true;

					for (int ri = 0; ri < 3; ri++)
					{
						unsigned short rlocks = lrlocks;
						for (int ti = 0; ti < 16; ti++)
						{
							if (lrlocks & (1 << ti))
								rlocks |= 1 << rotateTable[ti];
							else
								rlocks &= ~(unsigned short)(1 << rotateTable[ti]);
						}
						visited[rlocks] = true;
						lrlocks = rlocks;
					}
				}
			}
		}
		
		swap(nodes1, nodes2);
		swap(paths1, paths2);
		nodes2.clear();
		paths2.clear();
	}
}