AcWing 116. 飞行员兄弟
原题链接
简单
作者:
cytosine_6
,
2022-02-25 01:10:55
,
所有人可见
,
阅读 209
广搜+位运算 总共2^16状态 总时间3400ms左右
#include"iostream"
#include"queue"
#include"map"
using namespace std;
const int maxn = 1e5;
char mz[5][5];
bool vis[maxn];
int work(int tmp,int x,int y){
int k = 1<<(x*4);
for(int i=0;i<4;i++){
tmp^=(k<<i);
}
k = 1<<y;
for(int i=0;i<4;i++){
if(i==x) continue;
tmp^=(k<<(4*i));
}
return tmp;
}
int main(){
for(int i=0;i<4;i++){
cin>>mz[i];
}
int st=0;
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
if(mz[i][j]=='+'){
st|=(1<<(i*4+j));
}
}
}
queue<int>q;
q.push(st);
vis[st]=true;
map<int,pair<int,int> >f;
f[st] = {-1,-1};
int step=0;
while(!q.empty()){
int n = q.size();
bool flag =0;
for(int i=0;i<n;i++){
int cur = q.front();
q.pop();
if(cur==0){
flag =1;
break;
}
for(int i=0;i<4;i++){
for(int j=0;j<4;j++){
int tmp = work(cur,i,j);
if(!vis[tmp]){
f[tmp] = {cur,i*4+j};
q.push(tmp);
vis[tmp]= true;
}
}
}
}
if(flag) break;
++step;
}
cout<<step<<endl;
int ed =0;
vector<int>ans(step);
int i=0;
while(f[ed].first!=-1){
ans[i++] = f[ed].second;
ed = f[ed].first;
}
for(int j=step-1;j>=0;j--){
cout<<ans[j]/4+1<<" "<<ans[j]%4+1<<endl;
}
return 0;
}