BFS+位运算
900MS左右过了。。。
代码：
#include<iostream>
using namespace std;

#define HANDLES  16
#define MAX 65536
int Queue[MAX];
int front, rear; //队列Queue头尾游标
bool isVis[MAX]; //记录状态是否已经出现过
int step[MAX]; //记录到达成功状态所需翻转次数
int Move[MAX]; //记录BFS过程当前已改变的位置
int start, end;//队列Move头尾游标

//十进制转二进制
void output(unsigned int d, char *str) {
	int nStart = -1, i = 0;
	for (i = 0; i < 32; i++) {
		bool bOne = (0 != (d & (1 << (32 - i - 1))));
		if (bOne && nStart < 0) {
			nStart = i;
		}
		str[i - nStart] = bOne ? '1' : '0';
	}
	str[i - nStart] = '\0';
}

int main() {
	char bzero[HANDLES];
	char bzeroPut[HANDLES];

	for (int i = 0; i < HANDLES; ++i) {
		bzeroPut[i] = '0';
	}

	char ch;
	int state = 0;
	int stateTemp = 0;
	int move = 0;
	int moveTemp = 0;
	//'-' means open, '+' means closed.
	for (int i = 0; i < HANDLES; ++i) {
		cin >> ch;
		state <<= 1;
		if (ch == '-')
			state += 1;
	}

	start = end = front = rear = 0;
	Queue[rear++] = state; //将初始状态state入队
	isVis[state] = true;
	step[state] = 0; //到达初始状态所需次数为0

	//如果队列不为空，继续操作
	while (front < rear) {
		stateTemp = Queue[front++]; //将队头元素出队
		//保存队头元素到state中
		state = stateTemp;

		moveTemp = start < end ? Move[start++] : 0; //将队头元素出队
		move = moveTemp;
		//需要遍历队头元素的16种操作
		for (int site = 0; site < HANDLES; ++site) {
			//每次都要还原stateTemp
			stateTemp = state;
			//每次都要还原moveTemp
			moveTemp = move;

			/*******改变site位置的handle前，设置要改变的位置*******/
			int op = 0;
			int opTemp = 0;
			int x, y;//横纵坐标
			x = site / 4;
			y = site % 4;
			//改变一行
			for (int i = x * 4; i < (x + 1) * 4; ++i) {
				opTemp = 1;
				opTemp <<= (HANDLES - 1 - i);
				op += opTemp;
			}
			//改变一行和改变一列时重复改变了位置(x,y)，故需再进行一次改变
			opTemp = 1;
			opTemp <<= (HANDLES - 1 - site);
			op -= opTemp;
			//改变一列
			for (int j = y; j <= y + 12; j += 4) {
				opTemp = 1;
				opTemp <<= (HANDLES - 1 - j);
				op += opTemp;
			}
			/*******改变site位置的handle前，设置要改变的位置*******/

			//改变site位置的handle
			stateTemp ^= op;

			//判断是否成功
			if (stateTemp == 65535) {
				cout << step[state] + 1 << endl;
				//记录移动的位置
				opTemp = 1;
				opTemp <<= site;
				moveTemp |= opTemp;

				output(moveTemp, bzero);

				int bzeroLength = 0;
				while (bzero[bzeroLength] == '0' || bzero[bzeroLength] == '1')
					bzeroLength++;

				for (int i = bzeroLength - 1, j = HANDLES - 1; i >= 0 && j >= 0; i--, j--) {
					bzeroPut[j] = bzero[i] == '1' ? '1' : '0';
				}

				for (int i = HANDLES - 1; i >= 0; i--) {
					if (bzeroPut[i] == '1') {
						cout << (HANDLES - 1 - i) / 4 + 1 << " " << (HANDLES
								- 1 - i) % 4 + 1 << endl;
					}
				}
				return 0;
			}
			//如果是新的状态，入队
			if (!isVis[stateTemp]) {
				Queue[rear++] = stateTemp;
				isVis[stateTemp] = true;
				step[stateTemp] = step[state] + 1; //当前次数=到达队头元素所需次数  + 1
				//记录移动的位置
				opTemp = 1;
				opTemp <<= site;
				moveTemp |= opTemp;
				Move[end++] = moveTemp;
			}
		}
	}

	output(state, bzero);
	printf("%s\n", bzero);

	return 0;
}