a198: NOI2005 Day1.3.智慧珠游戏
Tags :
Accepted rate : 11人/11人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-11-01 03:13

Content

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

〇〇

〇〇〇

〇〇〇〇

〇〇〇〇〇

〇〇〇〇〇〇

〇〇〇〇〇〇〇

〇〇〇〇〇〇〇〇

〇〇〇〇〇〇〇〇〇

〇〇〇〇〇〇〇〇〇〇

图 1

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

 


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

符号为A,形状为

〇〇

 

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

符号为B,形状为

〇〇〇〇

符号为C,形状为

〇〇〇

符号为D,形状为

〇〇

〇〇

 

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

符号为E,形状为

〇〇〇

符号为F,形状为

〇〇〇〇

 

符号为G,形状为

〇〇〇

 

符号为H,形状为

〇〇〇

〇〇

符号为I,形状为

〇〇〇

  〇〇

符号为J,形状为

 

〇〇〇

 

符号为K,形状为

〇〇

 〇〇

符号为L,形状为

〇〇〇〇

 

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

 

  

   

    

     

      

 E E H H I I A

 L H H H I A A F

 L L L L I F F F F

图3

对于由珠子构成的零件,可以放到盘件的任一位置,条件是能有地方放,且
尺寸合适,所有的零件都允许旋转(0º、90º、180º、270º)和翻转(水平、竖直)。
现给出一个盘件的初始布局,求一种可行的智慧珠摆放方案,使所有的零件
都能放进盘件中。

Input

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

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

Output

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


如果无解,输出单独的一个字符串‘No solution’(不要引号,请注意大小写)。


所有的数据保证最多只有一组解。

Sample Input
.
..
...
....
.....
.....C
...CCC.
EEEHH...
E.HHH....
E.........
Sample Output
B
BK
BKK
BJKK
JJJDD
GJGDDC
GGGCCCI
EEEHHIIA
ELHHHIAAF
ELLLLIFFFF
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1K
公開 測資點#3 (10%): 1.0s , <1K
公開 測資點#4 (10%): 1.0s , <1K
公開 測資點#5 (10%): 1.0s , <1K
公開 測資點#6 (10%): 1.0s , <1K
公開 測資點#7 (10%): 1.0s , <1K
公開 測資點#8 (10%): 1.0s , <1K
公開 測資點#9 (10%): 1.0s , <1K
Hint :

感谢morris1028提供图片。

有些未删掉的多余信息,是为了让看不到图的人也能做。

Tags:
出處:
NOI2005Day1第三题 [管理者:
liouzhou_101 (王启圣)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」