这是个标题
Black White Chess
题目描述
一个4×4的格子棋盘，每个格子上有白棋或者黑棋，我们可以做下面三种操作：
把同一行的棋子翻转（白变成黑，黑变成白）
把同一列的棋子翻转
把一个2×2的格子里的棋子翻转
求最少多少步操作，我们可以得到全部是黑的或者全部是白的棋局。
输入
第一行是一个整数T(1≤T≤100000)，表示样例的个数。 以后每行一个样例，每行是一个16位的二进制码，依次表示从第1行到第4行的棋局。
输出
每行输出一个样例的结果，如果无法达到目标，输出“-1”。
样例输入
5
0000000000000000
1111111111111111
0000111100001111
1000000000000000
1100000000000011
样例输出
0
0
2
-1
4
BFS
思路：挺巧妙的，从全0和全1状态开始BFS出每种局面，因为局面最多2^16种，所以不会超时。对于每次查询，直接输出即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| #include<bits/stdc++.h>
using namespace std;
#define Debug(x) cout<<#x<<':'<<x<<endl
#define INF 0x7fffffff
typedef long long ll;
typedef pair<ll,ll> P;
const ll maxn=1e5+11;
ll vis[maxn],ans[maxn];
string row(string s,ll x){
for(ll i=4*(x-1);i<4*x;i++) s[i]=(s[i]=='0'?'1':'0');
return s;
}
string col(string s,ll x){
for(ll i=x-1;i<16;i+=4) s[i]=(s[i]=='0'?'1':'0');
return s;
}
string squ(string s,ll x){
ll b=(x-1)/3+x-1;
for(ll i=b;i<=b+1;i++) s[i]=(s[i]=='0'?'1':'0');
for(ll i=b+4;i<=b+4+1;i++) s[i]=(s[i]=='0'?'1':'0');
return s;
}
ll hash_1(string s){
ll sum=0;
for(ll i=0;i<s.length();i++) sum=sum*2+s[i]-'0';
return sum;
}
void bfs(){
queue<pair<string,ll>> q;
string s1,s2;
for(ll i=0;i<16;i++) s1+='0';
for(ll i=0;i<16;i++) s2+='1';
q.push({s1,0});q.push({s2,0});
while(!q.empty()){
string s=q.front().first;
ll dd=q.front().second;
q.pop();
ll x=hash_1(s);
if(vis[x]) continue;
vis[x]=1,ans[x]=dd;
for(ll i=1;i<=4;i++) q.push({row(s,i),dd+1});
for(ll i=1;i<=4;i++) q.push({col(s,i),dd+1});
for(ll i=1;i<=9;i++) q.push({squ(s,i),dd+1});
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
bfs();
ll ca;cin>>ca;
while(ca--){
string s;cin>>s;
ll x=hash_1(s);
if(vis[x]) cout<<ans[x]<<endl;
else cout<<-1<<endl;
}
return 0;
}
|