C0317 [NOI2005Day1-C]智慧珠游戏

内存限制:256 MB 时间限制:1000 ms

题目描述

智慧珠游戏拼盘由一个三角形盘件和12个形态各异的零件组成。拼盘的盘件如图所示

屏幕快照 2019-06-10 下午9.00.06.png

12个零件按珠子数分3大类:

第1大类,有三个珠子,只有一种形状。

  • 符号为A,形状为屏幕快照 2019-06-10 下午9.05.28.png

第2大类,有4个珠子,有3种形状。

  • 符号为B,形状为屏幕快照 2019-06-10 下午9.05.53.png
  • 符号为C,形状为屏幕快照 2019-06-10 下午9.06.03.png
  • 符号为D,形状为屏幕快照 2019-06-10 下午9.06.10.png

第3大类,有5个珠子,有8种形状。

  • 符号为E,形状为屏幕快照 2019-06-10 下午9.07.19.png
  • 符号为F,形状为屏幕快照 2019-06-10 下午9.07.26.png
  • 符号为G,形状为屏幕快照 2019-06-10 下午9.07.33.png
  • 符号为H,形状为屏幕快照 2019-06-10 下午9.07.41.png
  • 符号为I,形状为屏幕快照 2019-06-10 下午9.07.49.png
  • 符号为J,形状为屏幕快照 2019-06-10 下午9.26.14.png
  • 符号为K,形状为屏幕快照 2019-06-10 下午9.26.23.png
  • 符号为L,形状为屏幕快照 2019-06-10 下午9.26.32.png

下图示出了一种拼盘方案。为便于描述可进行抽象,就可以用一个数据为字符的二维数组来表示了。

屏幕快照 2019-06-10 下午9.28.20.png

屏幕快照 2019-06-10 下午9.28.28.png

对于由珠子构成的零件,可以放到盘件的任一位置,条件是能有地方放,且尺寸合适,所有的零件都允许旋转($0^{\circ}$、$90^{\circ}$、$180^{\circ}$、$270^{\circ}$)和翻转(水平、竖直)。

现给出一个盘件的初始布局,求一种可行的智慧珠摆放方案,使所有的零件都能放进盘件中。

输入格式

一共有10行,第$i$行有$i$个字符。如果第$i$行的第$j$个字符是字母“A”至“L”中的一个,则表示第$i$行第$j$列的格子上已经放了零件,零件的编号为对应的字母。如果第$i$行的第$j$个字符是“.”,则表示第$i$行第$j$列的格子上没有放零件。

输入保证预放的零件已摆放在盘件中。

输出

如果能找到解,打印10行,为放完全部12个零件后的布局。其中,第$i$行应包含$i$个字符,第$i$行的第$j$个字符表示第$i$行第$j$列的格子上放的是哪个零件。

如果无解,输出单独的一个字符串‘No solution’(不要引号,请注意大小写)。所有的数据保证最多只有一组解。

样例

样例输入 1

. .. ... .... ..... .....C ...CCC. EEEHH... E.HHH.... E.........

样例输出 1

B BK BKK BJKK JJJDD GJGDDC GGGCCCI EEEHHIIA ELHHHIAAF ELLLLIFFFF

提示