116. 飞行员兄弟

原题链接：116. 飞行员兄弟

解题思路

算法标签：位运算+二进制枚举

这道题目解题思路大致是，首先我们可以构造一个16位二进制数，然后，二进制数的每一位代表4x4矩阵中的一位，例如1代表(1,1),2代表(1,2),3代表(1,3),4代表(1,4),5代表(2,1)。既然这样的话，那么我们只需要枚举这个16位的二进制数，就可以确定我们的方案，因为题目只需要最优解方案，所以时间复杂度大约是O(16*2^16)

样例代码

#include <bits/stdc++.h>
using namespace std;
int a[21][21],i,j,k;
queue<pair<int,int> > ans2,ans1;
queue<pair<int,int> > kong; //空序列，用于清空序列 
int main()
{
    char ch;
    for (i=1; i<=4; i++)
    {
        for (j=1; j<=4; j++)
        {
            ch=getchar();
            if (ch=='-')
                a[i][j]=1;
        }
        getchar();
    }
//  cout<<c[1]<<endl<<c[2]<<endl<<c[3]<<endl<<c[4]<<endl;
    int ans=1e7;
    for (i=1; i<(1<<17); i++)
    {
        int b[5][5];
        for (j=1; j<=4; j++)
            for (k=1; k<=4; k++)
                b[j][k]=a[j][k];
        ans1=kong;
        for (j=1; j<=16; j++)
            if (i>>(j-1) & 1)
            {
                int dx=j%4,dy=j/4+1;
                if (j%4==0)
                    dx=4,dy--;
                for (k=1;k<=4;k++)
                    b[dy][k]^=1;
                for (k=1;k<=4;k++)
                    if (k!=dy)
                        b[k][dx]^=1;
                ans1.push(make_pair(dy,dx));
            }
        bool ok=true;
        for (j=1;j<=4;j++)
            for (k=1;k<=4;k++)
                if (!b[j][k])
                    ok=false;
        if (ok)
            break;
    }
    cout<<ans1.size()<<endl;
    while(!ans1.empty())
    {
        cout<<(ans1.front()).first<<" "<<ans1.front().second<<endl;
        ans1.pop();
    }
    return 0;
}