2069 - 翻木板
最近ayit举办了一场翻木板游戏比赛，游戏规则是这样的：有一个大机器，里面放一排共m（0<m<21）个木板,分别编号为0到m-1，机器外面有k（0<k<200）个按钮，每个按钮可以翻转一些木板，游戏开始时木板都是正面朝上，现在必须通过按钮把木板全部翻成反面朝上，谁用的次数最少就是获胜者。yaling童鞋参加了这个比赛，大家帮他算算完成这个游戏至少需要按多少次按钮。
Input
有多组测试数据。每组测试数据第一行为 m 和 k 。接下来有k行数字，代表k个按钮，每行数字的第一个数 n 代表相应的按钮可以翻转 n 个木板，随后又有 n 个数字，表示按钮可以翻转木板的编号。
Output
输出一个数字占一行，表示至少需要按按钮的次数。数据保证有解。
Examples
Input
3 2 1 0 2 1 2 3 3 2 0 1 1 1 2 1 2
Output
2 3
Hint
第二组测试数据：
比赛开始时木板的状态为： 正正正
按第一个按钮时变成 ： 反反正
按第二个按钮时变成 ： 反正正
按第三个按钮时变成 ： 反反反
Solution C++
#include <cstdio> #include <cstring> #include <queue> using namespace std ; int visit[5000000] ; int main() { // freopen("in.txt" , "r" , stdin ) ; int n ; int on[100010] ; while( ~scanf("%d" , &n ) ) { int k ; scanf("%d" , &k ) ; memset( on , 0 , sizeof( on ) ) ; memset( visit , -1 , sizeof( visit ) ) ; for( int i = 0 ; i < k ; i ++ ) { int t ; scanf("%d" , &t ) ; for( int j = 0 ; j < t ; j ++ ) { int m ; scanf("%d" , &m ) ; on[i] = on[i] | ( 1 << m ) ; } } queue<int> q ; q.push(0) ; visit[0] = 0 ; while( !q.empty() ) { int t = q.front() ; q.pop() ; for( int i = 0 ; i < k ;i ++ ) { int tt = t ^ on[i] ; if( visit[tt] == -1 ) { visit[tt] = visit[t] + 1 ; q.push( tt ) ; if(visit[(1<<n)-1] != -1) break ; } } if(visit[(1<<n)-1] != -1) break ; } if( visit[(1<<n)-1] != -1 ) { printf("%d\n" , visit[(1<<n)-1]) ; } else { printf("no solver!\n") ; } } return 0 ; }
Hint
第二组测试数据：
比赛开始时木板的状态为： 正正正
按第一个按钮时变成 ： 反反正
按第二个按钮时变成 ： 反正正
按第三个按钮时变成 ： 反反反