#P16508. [NEERC2009 Northern]Image Recognition

[NEERC2009 Northern]Image Recognition

题目描述

Irene 就职于 Novel Efforts in Effective Recognition of Characters(NEERC),她的新项目研究如何使用机器人识别图像。

为了先建立一个简单模型,她固定了 dd 幅图像,分别代表数字 0,1,,d10,1,\ldots,d-1。每幅图像都是一个高为 hh、宽为 ww 的矩形,由黑色或白色的单位方格组成。任意两幅图像至少有一个像素不同。

机器人被放在其中一幅图像的左上角像素上,然后执行使用下列语言编写的程序。机器人的目标是判断自己位于哪一幅图像上。

程序语言包含以下命令:

  • UDLR:移动命令,分别令机器人向上、下、左、右移动一个像素。若机器人移出图像范围,则任务失败;
  • (子程序W:子程序B):条件语句。机器人检查当前像素的颜色;若为白色,则执行冒号左侧的子程序,否则执行冒号右侧的子程序;
  • 01、……、9:识别命令。当机器人已经确定图像编号后,执行相应数字命令并立即终止程序。

每条移动命令消耗一个单位时间;条件判断和识别命令均不消耗时间。

一个程序是正确的,当且仅当对于每个 ii,机器人放在代表数字 ii 的图像上时,程序最终都会执行命令 i

请构造一个始终正确的程序,并使其在所有图像上的执行时间最大值最小。

输入格式

第一行包含三个整数 d,h,wd,h,w,分别表示图像数量、每幅图像的高度和宽度。

接下来依次给出代表数字 0,1,,d10,1,\ldots,d-1dd 幅图像。

每幅图像由 hh 行长度为 ww 的字符串描述,其中:

  • B 表示黑色像素;
  • W 表示白色像素。

相邻两幅图像之间由一个空行分隔。

输出格式

输出一个正确的机器人程序,使其最坏情况下的执行时间最小。

若存在多个最优程序,输出任意一个即可。

解析输出程序时,所有空白字符都会被忽略。

数据范围

  • 1d101\le d\le 10
  • 1h,w101\le h,w\le 10
  • 所有图像互不相同。

样例

输入

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. 若该像素为白色,则识别为图像 1
  3. 否则再向下移动一格并检查像素,白色对应图像 2,黑色对应图像 0