游客 注册 | 登录
中文 | En

2069 - 翻木板

通过次数

0

提交次数

0

时间限制 : 3 秒 内存限制 : 128 MB

    最近ayit举办了一场翻木板游戏比赛，游戏规则是这样的：有一个大机器，里面放一排共m（0<m<21）个木板,分别编号为0到m-1，机器外面有k（0<k<200）个按钮，每个按钮可以翻转一些木板，游戏开始时木板都是正面朝上，现在必须通过按钮把木板全部翻成反面朝上，谁用的次数最少就是获胜者。yaling童鞋参加了这个比赛，大家帮他算算完成这个游戏至少需要按多少次按钮。

题目输入

有多组测试数据。每组测试数据第一行为 m 和 k 。接下来有k行数字，代表k个按钮，每行数字的第一个数 n 代表相应的按钮可以翻转 n 个木板，随后又有 n 个数字，表示按钮可以翻转木板的编号。

题目输出

输出一个数字占一行，表示至少需要按按钮的次数。数据保证有解。

输入/输出样例

输入格式

3 2
1 0
2 1 2
3 3
2 0 1
1 1
2 1 2

输出格式

2
3

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 ;
}

Java解答

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
	int m,k;
	int[] B;
	
public Main() {
	Scanner sc=new Scanner(System.in); //sc.hasNextInt();
	while(sc.hasNextInt()) {
		m=sc.nextInt(); k=sc.nextInt();
		int start=(1<<m)-1;
		B=new int[k];
		for(int i=0;i<k;i++) {
			int zero=0;  //000
			            //001 按钮 翻转0号位   最右边一位
			int n=sc.nextInt();
			for(int a=0;a<n;a++)
			{
				int temp=sc.nextInt();
				zero=zero|(1<<temp); //把第temp位上设置为1
			}
			B[i]=zero;
			//System.out.println(zero);
		}
		
		ArrayList<Node> AL=new ArrayList<Node>();  //队列
		
		Node startnode=new Node(start,0);  startnode.Mark='S';//加上开始标记s
		Node goalnode=new Node(0,0);        goalnode.Mark='G';  //加上终止拓展标记G
		HashMap<Integer,Node> StartSet=new HashMap<Integer,Node>(); StartSet.put(start,startnode);//开始格局 映射到startnode
		HashMap<Integer,Node> GoalSet=new HashMap<Integer,Node>(); GoalSet.put(0,goalnode);//目标格局 映射到goalnode
		
		AL.add(startnode);  AL.add(goalnode); //开始状态和目标状态加入队列
		int index=0; boolean success=true;
		while(index<AL.size() && success) {
			Node current=AL.get(index);
			if(current.Mark=='S'&&GoalSet.containsKey(current.align)) //判断是否目标状态
			{
				System.out.println(current.step+GoalSet.get(current.align).step); success=false;  break;
			}
			if(current.Mark=='G'&&StartSet.containsKey(current.align)) //判断是否目标状态
			{
				System.out.println(current.step+StartSet.get(current.align).step); success=false;  break;
			}
			
			for(int i=0;i<k;i++) {
				int newalign=current.align^B[i]; //按下按钮，翻转
				
				
				if(current.Mark=='S'&&StartSet.containsKey(newalign)==false||current.Mark=='G'&&GoalSet.containsKey(newalign)==false) {
					Node newstate=new Node(newalign,current.step+1);
					newstate.Mark=current.Mark;
					AL.add(newstate);
					if(newstate.Mark=='S') StartSet.put(newalign,newstate);
					else GoalSet.put(newalign, newstate);
					
				}
				
			}
			
			index++;
		}
	}
}
		

	public static void main(String[] args) {
		// TODO Auto-generated method stub
Main tk=new Main();
	}

    class Node{
		public Node(int a,int s) {
			align=a;step=s;
		}
		int align; //排列
		int step;  //步数
		char Mark;//标记开始拓展 还是  结束拓展
	}
}
请先登陆