/ Vijos / 题库 /

zgx的神奇机器

zgx的神奇机器

背景

zgx也就是我,有一个猥琐的胶片提取机,该机器有三个放胶片的对:堆1,堆二,堆Ⅲ。每个微缩胶片有一个二进制编号,胶片的编号被打在了胶片的外框上。

胶片左侧有g个单元,每个单元对应编号是一个二进制位。如果某个单元的对应位为1,那么该单元的位置是一条缝,否则该位置上是一个孔。

描述

初始的胶片全在堆1中,现在要从中挑一张特定编号的胶片。这台机器只给你一种操作:
move(i,k,j):表示将堆i中所有编号第k位是孔的胶片移动到堆j中。

你的任务是用最少的操作步数使得目标胶片单独处于机器的某一堆中。

格式

输入格式

第一行,n(1<=n<=10000,胶片数)、g(1<=g<=15);
接下来n行,每行一个g位的二进制数,表示一个胶片的编号。第一个出现的是目标胶片。

输出格式

一行,最少移动步数。

若永远不可能实现则输出“No way”。

样例1

样例输入1

4 3
010
011
100
110

样例输出1

2

限制

各个测试点1s

提示

不算难题,下一题才是^_^

信息

ID
1563
难度
9
分类
其他 | 构造搜索 | 枚举搜索 点击显示
标签
递交数
429
已通过
29
通过率
7%
被复制
3
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

zgx第一次模拟赛