bzoj1080

传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1080

神暴力,待搞懂.

代码

#include <cstdio>

#include <cmath>

#include <iostream>

#include <cstring>

#include <algorithm>

#include <vector>

#include <map>

#include <queue>

#define ll long long

using namespace std;

typedef vector<int> ve;

map <ve,int> hash;

queue<ve>q;

string s[35];

int n;

void work()

{

    ve u,v,t;

    for (int i=1;i<=n;i++)

        if (s[i]=="")

        {

            printf("0");

            exit(0);

        }

        else u.push_back(i<<6);

    hash[u]=0;

    for(q.push(u);!q.empty();)

    {

        u=q.front();

        q.pop();

        int x=hash[u],cnt;

        for (int ch='0';ch<='1';ch++)

        {

            cnt=0;

            v.clear();

            for (int i=0;i<u.size();i++)

            {

                int which=u[i]>>6,where=u[i]&63;

                if (s[which][where]^ch) continue;

                if(++where==s[which].size()) {

                    ++cnt;

                for (int j=1;j<=n;j++)v.push_back(j << 6);

                }else v.push_back(which<<6|where);

            }

            if(cnt>=3)

            {

                printf("%d",x+1);

                exit(0);

            }

            sort(v.begin(),v.end());

            t.clear();

            for (int i=0;i<v.size();i++)

            {

                if(i<3||v[i]^v[i-3]) t.push_back(v[i]);

            }

            int &th=hash[t];

            if (t.size()&&!th) th=x+1,q.push(t);

        }

    }

    printf("-1");

}

int main()

{

    scanf("%d",&n);

    for (int i=1;i<=n;i++) cin>>s[i];

    work();

    return 0;

}