JOIN
Get Time

   Problem Statement  

 Problem Statement for ConnectingGame

Problem Statement

    

Cat Snuke and wolf Sothe are playing the Connecting Game.



The Connecting Game is played on a rectangular grid that is divided into unit square cells. The grid is divided into some regions. Each cell belongs into exactly one of those regions. Each region is 4-connected (see Notes for a formal definition).



You are given a String[] board that describes the division of the grid into regions. Each character in board represents one of the cells. Cells that are represented by the same character belong into the same region.



Initially, the entire grid is colorless. During the game, the players color some of the regions red and other regions blue. (Within each region, all cells must have the same color.) The game ends when the entire board is colored. The actual rules of the game are not important. The only information you need is that at the end of the game each combination of red and blue regions is possible.



At the end, the game is evaluated as follows:

  • If there is a path (see Notes for a formal definition) of blue cells from the top row to the bottom row, Snuke wins.
  • If there is a path of red cells from the left column to the right column, Sothe wins.


Obviously, it is impossible for both players to win the game at the same time. However, sometimes there can be no winner. Your task is to recognize game boards for which this may happen.



Formally, a board is called valid if it is guaranteed that the game will have a winner, and invalid if it is possible that there is no winner at the end of the game. You are given the String[] board. Return "valid" (quotes for clarity) if it represents a valid board, or "invalid" if it does not.

 

Definition

    
Class:ConnectingGame
Method:isValid
Parameters:String[]
Returns:String
Method signature:String isValid(String[] board)
(be sure your method is public)
    
 

Notes

-A path is a sequence of cells such that each pair of consecutive cells shares a common side.
-A region is 4-connected if for any two cells A and B in that region there is a path that starts with A, ends with B, and only contains cells from that region.
 

Constraints

-board will contain between 1 and 30 elements, inclusive.
-Each element in board will contain between 1 and 30 characters, inclusive.
-All elements in board will have the same length.
-Each character in board will be a letter or a digit ('a'-'z', 'A'-'Z', or '0'-'9').
-Each of the regions in board will be 4-connected.
 

Examples

0)
    
{"AAB"
,"CCD"}
Returns: "invalid"
If the players color regions A and D red and regions B and C blue, no player wins. Hence, this board is invalid.
1)
    
{"AA"
,"BB"}
Returns: "valid"
2)
    
{"iii"
,"iwi"
,"iii"}
Returns: "valid"
3)
    
{"SSnukee"
,"SKnuthe"
,"SSSothe"}
Returns: "invalid"
4)
    
{"rng58"
,"rnggn"
,"rnnnn"}
Returns: "valid"
5)
    
{"ggssGGGGGG","ggssspGGGG","ggsssppGGG","ggWsspGGGG","gggsspGGiG","g7ssspGGGG","gggsseKK33","gggssssK33","gHgsssHA33","HHHHHHHHHH","HHHHHHHHH6","HHHHHHHHb6"}
Returns: "invalid"

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 637 Round 1 - Division I, Level Three