#P16508. [NEERC2009 Northern]Image Recognition
[NEERC2009 Northern]Image Recognition
题目描述
Irene 就职于 Novel Efforts in Effective Recognition of Characters(NEERC),她的新项目研究如何使用机器人识别图像。
为了先建立一个简单模型,她固定了 幅图像,分别代表数字 。每幅图像都是一个高为 、宽为 的矩形,由黑色或白色的单位方格组成。任意两幅图像至少有一个像素不同。
机器人被放在其中一幅图像的左上角像素上,然后执行使用下列语言编写的程序。机器人的目标是判断自己位于哪一幅图像上。
程序语言包含以下命令:
U、D、L、R:移动命令,分别令机器人向上、下、左、右移动一个像素。若机器人移出图像范围,则任务失败;(子程序W:子程序B):条件语句。机器人检查当前像素的颜色;若为白色,则执行冒号左侧的子程序,否则执行冒号右侧的子程序;0、1、……、9:识别命令。当机器人已经确定图像编号后,执行相应数字命令并立即终止程序。
每条移动命令消耗一个单位时间;条件判断和识别命令均不消耗时间。
一个程序是正确的,当且仅当对于每个 ,机器人放在代表数字 的图像上时,程序最终都会执行命令 i。
请构造一个始终正确的程序,并使其在所有图像上的执行时间最大值最小。
输入格式
第一行包含三个整数 ,分别表示图像数量、每幅图像的高度和宽度。
接下来依次给出代表数字 的 幅图像。
每幅图像由 行长度为 的字符串描述,其中:
B表示黑色像素;W表示白色像素。
相邻两幅图像之间由一个空行分隔。
输出格式
输出一个正确的机器人程序,使其最坏情况下的执行时间最小。
若存在多个最优程序,输出任意一个即可。
解析输出程序时,所有空白字符都会被忽略。
数据范围
- ;
- ;
- 所有图像互不相同。
样例
输入
3 5 4
WBBW
BWWB
BWWB
BWWB
WBBW
WWBW
WBBW
BWBW
WWBW
WWBW
WBBW
BWWB
WWBW
WBWW
BBBB
输出
D(1:D(2:0))
样例中的三幅图像如下:

说明
程序 D(1:D(2:0)) 的含义是:
- 先向下移动一格并检查当前像素;
- 若该像素为白色,则识别为图像
1; - 否则再向下移动一格并检查像素,白色对应图像
2,黑色对应图像0。