← 返回题目列表

AtCoder · icpc2014autumn_k

K. 幂等过滤器

中文机器翻译题面 查看原题

问题陈述

让我们考虑对由六边形像素组成的单色图像的操作,每个像素都是黑色或白色。由于像素的形状,每个像素都有六个邻居(例如与其共享边缘的像素。)

“过滤”是一种根据像素本身及其六个邻居的颜色确定像素颜色的操作。过滤示例如下所示。

示例 1:当某个像素的所有相邻像素均为白色时,该像素的颜色为白色。否则颜色不会改变。

[原图]

同时对所有像素执行此操作会产生“噪声消除”,从而消除孤立的黑色像素。

示例 2:当某个像素的所有相邻像素均为黑色时,该像素的颜色为白色。否则颜色不会改变。

[原图]

对所有同时像素执行此操作会导致“边缘检测”,仅留下填充区域的边缘。

示例 3:使用其正下方像素的颜色为像素着色,忽略任何其他相邻像素。

[原图]

对所有同时像素执行此操作会导致整个图像“上移”一个像素。

对任何图像应用某些过滤器(例如“噪声消除”和“边缘检测”)两次会产生与仅应用一次完全相同的结果。 我们称这样的过滤器为 幂等。 “上移”过滤器不是幂等的,因为每次重复应用都会将图像上移一个像素。

您的任务是确定给定的过滤器是否是幂等的。


输入

输入由多个数据集组成。数据集数量不到 100 美元。 每个数据集都是一个表示过滤器的字符串,并具有以下格式(数字之间没有空格)。

$c_0c_1\cdots{}c_{127}$

$c_i$ 为“0”(表示黑色)或“1”(表示白色),表示当像素及其相邻六个像素的二进制表示为 $i$ 时该像素的滤波器的输出。 从像素到比特的映射如下:

[原图]

且二进制表示 $i$ 定义为 $i = \sum_{j=0}^6{\mathit{bit}_j \times 2^j}$, 其中,如果相应像素为黑色或白色,则 $\mathit{bit}_j$ 分别为 $0$ 或 $1$。 请注意,滤波器应用于中心像素,表示为位 3。

输入以仅包含单个“#”的行结束。

输出

对于每个数据集,打印“yes" 如果给定的过滤器是幂等的,则在一行中,或者 "no”否则(引号是为了清楚起见)。


示例输入

00000000111111110000000011111111000000001111111100000000111111110000000011111111000000001111111100000000111111110000000111111111
10000000111111110000000011111111000000001111111100000000111111110000000011111111000000001111111100000000111111110000000011111111
01010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101
#

样本输入的输出

yes
yes
no