The Magic WhiteBoard
All submissions for this problem are available.
The Electronics and Communication department at Thapar is developing a new game.
The game consists of a board. The board contains NxN squares/blocks (i.e N blocks width wise and N blocks length wise). The blocks can have any color apart from white. The game goes this way, if you touch any block(say its color is C) it will change to white and all the surrounding blocks that will have color C will change to white and all the blocks surrounding them and having color C will change to white and so on. Once this stops, again you can touch any block and this will start the same process for that particular color. You have to calculate the number of touches required to change the color of whole board to white.
Any block can have atmost four blocks surrounding it (i.e. the one above it, the one below it, the one to its left and the one to its right).
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
- Each test case will contain a single number N, Then N lines follow.
- Each line will contain a string of length N. Giving the description of the colors on the board.
- For each test case output the minimum number of touches required separated by new line.
- 0 < T <= 10
- 1 < N <= 100
- 0 < Number of different Colors <= 100
Input: 2 5 RRBBB RRBBB RBGGG RGGGG RGGGG 6 GGGGGG GOOOOG GBBBBG GBBBBG GOOOOG GGGGGG Output: 4 4
Example case 1.
1) Suppose you touch a R The board will become WWBBB WWBBB WBGGG WGGGG WGGGG 2) Now you touch a B block(anyone one in the top row) WWWWW WWWWW WBGGG WGGGG WGGGG 3) Now touch a G block WWWWW WWWWW WBWWW WWWWW WWWWW 4) Now touch the only blue block left WWWWW WWWWW WWWWW WWWWW WWWWW
|Time Limit:||0.28 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.