【gzoj综合】五香豆腐【BFS+位运算】

【gzoj综合】五香豆腐【BFS+位运算】

题意

给出n个 5 ∗ 5 5*5 5∗5 的01矩阵，对一个点的一次操作就可以使本身和上下左右的位置都取反，回答n次当前矩阵能否在6次操作之内变成全1矩阵，输出这个步数，否则输出-1。

分析

看到01就想到压状态，数组只要开 2 25 2^{25} 225 就行。我们做一个反向广搜，也就是从全1矩阵开始搜索到所有能到的状态，因为这个操作是可逆的，所以就可以得知这些状态也能变回全1矩阵。经过这个预处理打表，就可以对于每个矩阵 O ( 1 ) O(1) O(1) 出解。

对于如何取出每一位应该很简单，取反操作就用异或实现就行。

然后发现空间限制65536kb，直接爆掉空间了。然后想想把int变成short，还是不行，差一点点，但是没法压了。想了好久。。。

想到步数只能是个位数，所以记录步数的数组可以开char！只要把步数用ASCII码存进去就可以了。于是就顺利通过此题。

上代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;const int wake=(1<<25)-1;
int n;
char step[1<<25];//看到步数很少，用char压空间(%yzr) int get(int x,int y)
{return (x-1)*5+(y-1);}void bfs()
{queue<int> q;q.push(wake);step[wake]='0';while(!q.empty()){int x=q.front();q.pop();if(step[x]<'6'){for(int i=1;i<=5;i++){for(int j=1;j<=5;j++){int bt=get(i,j),now=x;now^=(1<<bt);if(i>1) now^=(1<<(bt-5));if(i<5) now^=(1<<(bt+5));if(j<5) now^=(1<<(bt+1));if(j>1) now^=(1<<(bt-1));if(!step[now]){step[now]=step[x]+1;q.push(now);}}}}}
}int main()
{bfs();cin>>n;while(n--){int ask=0;for(int i=1;i<=25;i++){char c;cin>>c;ask=(ask<<1)+(c-48);}if(step[ask]==0) cout<<-1<<endl;else cout<<(int)(step[ask]-48)<<endl;}return 0;
}