P2622 关灯问题II(状态压缩 搜索)

关灯问题II - 洛谷https://www.luogu.com.cn/problem/P2622状态压缩的一个学习案例，一道很经典的题目。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <set>
#include <cmath>
#include <map>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int MN = 65005;
const int MAXN = 1e6 + 10;
const int INF = 0x3f3f3f3f;
#define IOS ios::sync_with_stdio(false)
#define lowbit(x) ((x)&(-x))
using P = pair<int, int>;


int n, m;
int a[1005][1005];
bool vis[MAXN];
void bfs() {
	queue<P> que;
	int s = (1 << n) - 1;
	vis[s] = true;
	que.push(P(s, 0));
	while (!que.empty()) {
		P t = que.front();
		que.pop();
		if (t.first == 0)
			return void(printf("%d", t.second));
		for (int i = 1; i <= m; i++) {
			int tmp = t.first;
			for (int j = 1; j <= n; j++) {
				if (a[i][j] == 1 && (1 << (j - 1)&tmp))
					tmp ^= 1 << (j - 1);
				else if (a[i][j] == -1 && !(1 << (j - 1)&tmp))
					tmp |= 1 << (j - 1);
			}
			if (!vis[tmp]){
				que.push(P(tmp, t.second + 1));
				vis[tmp]=1;
				}
		}
	}
	printf("-1\n");
}


int main() {
	int t;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%d", &a[i][j]);
		}
	}
	bfs();
	return 0;
}