网址:https://www.acwing.com/problem/content/97/
给出一个$5×5$的$01$矩阵,翻转一个点时,其上下左右合法的点都会被翻转,给出一个状态,问你能不能在$6$步的范围内使所有的元素都变成$1$。每个测试点最多$500$组数据。
如果直接$dfs$,那么对于一个矩阵,其时间复杂度是$O(C^{6}_{25})$,$500$个矩阵就会超时,所以我们使用一个队列进行$bfs$,记录$bfs$的层数。记录的方法是,对于一个没有出现过的局势,其层数为转移得到这个状态的状态的层数$+1$并压入队列,然后一旦队列中出现这个状态的层数是$6$则退出(这意味着队列中其他的状态都是$6$,其再进行$bfs$将会记录翻转了$7$次的状态,而这个不合法)。然后读入这些状态,判断其$bfs$的层数即可。
AC代码:
#include <bits/stdc++.h>using namespace std;int mp[1 << 25];int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };bool check(int x, int y){ if (x < 0 || x > 4 || y < 0 || y > 4) return 0; return 1;}int _hash(int x, int i){ int px = i / 5, py = i % 5; for (int i = 0; i < 4; ++i) if (check(px + dir[i][0], py + dir[i][1])) x ^= 1 << ((px + dir[i][0]) * 5 + py + dir[i][1]); x ^= (1 << i); return x;}void bfs(){ queue<int>que; mp[(1 << 25) - 1] = 1; que.push((1 << 25) - 1); while (!que.empty()) { int u = que.front(); que.pop(); if (mp[u] == 7) return; for (int i = 0; i < 25; ++i) { int v = _hash(u, i); if (!mp[v]) { mp[v] = mp[u] + 1; que.push(v); } } }}int main(){ bfs(); int T; scanf("%d", &T); while (T--) { int x = 0, a; for (int i = 0; i < 25; ++i) { scanf("%1d", &a); x ^= (a << i); } printf("%d\n", mp[x] - 1); } return 0;}