Black White Chess

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

近来,小X的朋友小S迷上了一种他自己发明的智力游戏—摆黑白棋游戏。游戏在方形棋盘进行的,这种棋盘随手可得,随便拿出一张纸画上方块形即可,如没纸就在地上甚至在手心里画都可以。棋子有黑白两种。有了棋盘,小S就在棋盘上随意摆上若干黑白棋子,他马上要小X按照他研究出来的摆黑白棋规则摆棋子,要求在最少步数内清除所有棋子。在小X摆棋时,小S可得意了,因为有些初始棋谱够为难小X了。嘿嘿!你看小S脸上多么灿烂。

小S的黑白棋规则如下:

1.每一步游戏用同一种颜色的棋子(黑或白棋)只对同一行或只对同一列的所有位置进行摆放操作。
2.如●、○、□分别表示棋盘上黑棋、白棋和空(无棋子),那么
○ + ● = □ ● + ● = ○ □ + ● = ●
○ + ○ = ● ● + ○ = □ □ + ○ = ○

如小S给了如下棋谱:
□ ● ● ●
○ □ □ □
○ □ □ □
○ □ □ □

小X只需用2步就能把所有棋子清除:先用白棋放第1行,再用黑棋放第1列即可。

Input

输入文件中有若干个棋谱的测试数据(个数不超过20)。

每组测试数据的第1行是一个正整数n,表示一个n*n棋盘,(n<30)。

接下来的n行描述一个棋谱,每一行均由B、W、0构成的长为n的字符串,注意0是数字,看清啦!

输入直到文件结束。

Output

对输入中的每组测试数据,先在一行上输出“Chess Board #:”,其中“#”是测试数据的组号(从1开始)。再在下一行输出清空棋盘所用的次数,如无法清空,则输出“Impossible”,否则先输出“Times=”,再输出步数。

Sample Input

4
0WWW
B000
B000
B000
4
W0W0
BB0B
0000
0000

Sample Output

Chess Board 1:
Times=2
Chess Board 2:
Impossible

Hint

知识扩展:黑白棋游戏,同样属于益智类游戏,设计一个好的算法直接和游戏的关卡、难度相关,由于手机软件开发的要求高于普通计算机软件开发,算法的高效性,直接决定了软件运行的效率和用户体验。

Source