1090: Y2K Bug and Bill Door

In the late 1999, Mr. Y2K Bug announced that he had got the power to control all the computer systems in the world. And In the year 2000, he will put all the world under his control with this powerful weapon. This had put many people in nightmare. It is almost the middle of year 2000 now. Most of us think that Mr. Bug is a liar and it is not dangerous any more. But in the world’s most popular Hardware Company MicroHard, the engineers has found that the Y2K bug still has some power to control their famous system Doors. So they try their best to catch Mr. Y2K Bug, want to kill him before he do real harm to the systems and control the world. But for a long time they can just see Mr. Bug’s tail. And Mr. Bug is also tired of the escaping life. So he breaks into the headquarter of MicroHard, and catch the boss Mr. Bill Door. And finally they make a deal that Mr. Y2K Bug will play a game with Mr. Bill Door. If Mr. Bug wins, he can control the world. But if Mr. Door wins, Mr. Bug must disappear forever. It is a one-player game. And it’s quite simple. It uses a square board with n*n boxes and some black stones and white stones. When the game starts, the boxes on the board are all empty. The player can put 1 stones into each of the n boxes of one row or one column. The n stones are not necessarily in same color. But one box cannot hold stones with different colors in one time. If the player put a stone into a box with different color stones, he must take out a white stone and a black stone immediately. Mr. Bug and Mr. Door agree that they will be given a target randomly, and each of them will play this game one time. The one get to the target with fewer turns will win. The target will be given with the board’s status like this: ....B ....B ....B ....B WWWW. This is a 5*5 board’s status, which “.” denotes a empty box, “B” denotes a box with black stones, “W” denotes a box with white stones. Mr. Door wants to win very much. So he decides to use pocket Door System to beat Mr. Bug. You, as a programmer is asked to write a program to find out how many turns must be taken to get to the given target at least.

The input file of your program contains more than one target. Each target starts with a line with only one integer n denote the size of the n*n board (n<=10). And the next n lines are the board status shown above. Each line contains n characters (“.”, “B” or “W”). A target with n=0 ends the input file. There is no leading and trailing space in each line. And no blank lines between targets.

Your program should output at least how many turns must be taken to get to the given target for each target like the sample output.

5
....B
....B
....B
....B
WWWW.
0

2