学霸的迷宫

妙妙屋 · 2020-07-24 19:19:54 · 个人记录

#include <cstdio>
#include <cstdlib>
#include <queue>

using namespace std;

int G[25][25],vis[2 << 22],n,init;
queue<int> q;

#ifndef ONLINE_JUDGE
void print_by_2(int val)
{
    char buf[256];
    itoa(val,buf,2);
    puts(buf);
}
#endif

int press(int val,int bnt)
{
    for (int i = 1;i <= G[bnt][0];++i)
        val &= ~(1 << (n - G[bnt][i]));
    val |= (1 << (n - bnt));
    return val;
}

void bfs()
{
    while (!q.empty())
    {
        int cur = q.front();q.pop();
        if (cur == (1 << (n - 3)))
            return ;
        for (int i = n - 1;i >= 0;--i)
        {
            if (!(cur & (1 << i)))
            {
                int s = press(cur,n - i);
                //print_by_2(s);
                if (!vis[s])
                {
                    vis[s] = vis[cur] + 1;
                    q.push(s);
                }
            }
        }
    }
}

int main()
{
    scanf("%d",&n);
    for (int i = 1;i <= n;++i)
    {
        int x;
        scanf("%d",&x);
        if (x == 1)
            init |= (1 << (n - i));
    }
    for (int i = 1;i <= n;++i)
    {
        int len;
        scanf("%d",&len);
        G[i][0] = len;
        for (int j = 1;j <= len;++j)
            scanf("%d",&G[i][j]);
    }
    q.push(init);
    bfs();
    printf("%d",vis[1 << (n - 3)]);
    return 0;
}