费解的开关（BFS+状态压缩）

PS：代码超时的，可惜。正解好像是DP，很好奇为什么DFS能卡过而BFS不行

题目链接：费解的开关

题目描述

你玩过“拉灯”游戏吗？25盏灯排成一个5x5的方形。每一个灯都有一个开关，游戏者可以改变它的状态。每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。

我们用数字“1”表示一盏开着的灯，用数字“0”表示关着的灯。下面这种状态

10111
01101
10111
10000
11011

在改变了最左上角的灯的状态后将变成：

01111
11101
10111
10000
11011

再改变它正中间的灯后状态将变成：

01111
11001
11001
10100
11011

给定一些游戏的初始状态，编写程序判断游戏者是否可能在6步以内使所有的灯都变亮。

输入格式

第一行输入正整数n，代表数据***有n个待解决的游戏初始状态。

以下若干行数据分为n组，每组数据有5行，每行5个字符。每组数据描述了一个游戏的初始状态。各组数据间用一个空行分隔。

输出格式

一共输出n行数据，每行有一个小于等于6的整数，它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。

对于某一个游戏初始状态，若6步以内无法使所有灯变亮，则输出“-1”。

数据范围

0<n≤500

输入样例：

3
00111
01011
10001
11010
11100

11101
11101
11110
11111
11111

01111
11111
11111
11111
11111

输出样例：

3
2
-1

思路

反向bfs，因为我们要搜的是搜索树中的其中一个边界，而我们得到的只是状态搜索树的其中一个节点，bfs的话可能会把双边的情况都考虑到，这样就可能爆内存，而从结果反向搜起点就没有这种多余的枚举。用map把重复的状态删除，这个图的状态可以压缩再一个25位的整数中。只可惜TLE了

C++ 代码

#include <bits/stdc++.h>

using namespace std;
int dir[4] = {1,-1,5,-5};
int num;
map<int,int> mp;
struct Node {
	int step;
	int now;
	
	Node(){}
	
	Node (int step, int now) {
		this->step = step;
		this->now = now;
	}
	
	Node operator = (const Node& A) {
		step = A.step;
		now = A.now;
		return *(this);
	}
	
	void change (int idx) { //灯状态变换
		this->now ^= (1 << (25 - idx));
		for (int i = 0; i < 4; i++) {
			int op = idx + dir[i];
			if (op < 1 || op > 25 || abs(idx-op) == 1 && abs(idx+op) % 10 == 1) {
				continue;
			}
			this->now ^= (1 << (25 - op));
		}
		
		this->step++;
	}
	
	bool isok () {
		if (now == num) {
			return true;
		}
		return false;
	}
	
};

queue<Node> Q;
int BFS (int s) {
	Node ths(0, s),nxt;
	while (!Q.empty()) {
		Q.pop();
	}
	mp.clear();
	mp.insert(make_pair(s,1));
	Q.push(ths);
	while (!Q.empty()) {
		ths = Q.front();
		Q.pop();
		for (int i = 1; i <= 25; i++) {
			nxt = ths;
			nxt.change(i);
			if (nxt.isok()) {
				return nxt.step;
			} else if (nxt.step < 6 && mp.find(nxt.now) == mp.end()){
				Q.push(nxt);
				mp.insert(make_pair(nxt.now, 1));
			}
		}
	}
	return -1;
}

int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		num = 0;
		for (int i = 0; i < 5; i++) {
			getchar();
			for (int j = 0; j < 5; j++) {
				char ch = getchar();
				num <<= 1;
				num |= (ch - '0');
			}
		}
		getchar();
		printf("%d\n",BFS((1 << 25)-1));
	}
	return 0;
}