TopCoder problem "WordsGame" used in SRM 454 (Division II Level Two)



Problem Statement

    You are playing a game with a NxN grid of letters. The goal of the game is to spell out a N-letter word somewhere on the grid either horizontally from left to right or vertically from top to bottom. To achieve this, you will perform a series of moves. On each move, you can swap either two rows or two columns of the grid.

You are given a String[] grid containing the initial state of the grid. The j-th character of the i-th element of grid is the letter at row i, column j. The word you must spell is given to you in the String word. All letters in word are distinct. Note that lowercase and uppercase versions of the same letter are considered different in this problem, so 'A' and 'a' are distinct. Return the minimal number of moves required to spell the given word on the grid, or -1 if it is impossible.
 

Definition

    
Class:WordsGame
Method:minimumSwaps
Parameters:String[], String
Returns:int
Method signature:int minimumSwaps(String[] grid, String word)
(be sure your method is public)
    
 

Constraints

-word will contain between 1 and 50 letters ('a'-'z', 'A'-'Z'), inclusive.

-All characters in word will be distinct.

-The number of elements in grid will be equal to the length of word.

-The length of each element of grid will be equal to the length of word.

-Each element of grid will contain only letters ('a'-'z', 'A'-'Z').
 

Examples

0)
    
{"Mu",
 "uM"}
"Mu"
Returns: 0
The first row of the grid already contains the required word.
1)
    
{"sdf",
 "bca",
 "hgf"}
"abc"
Returns: 2
First we swap first and third column. Then we swap second and third column. The resulting grid contains word "abc" in the second row. There is no way to do that in less than two swaps so we return 2.
2)
    
{"cdf",
 "bca",
 "agf"}
"abc"
Returns: 1
We could perform the same two swaps to get word "abc" in the second row. However, swapping first and third row results in a grid containing word "abc" in the first column so we return 1.
3)
    
{"xSZB",
 "gbHk",
 "kbgH",
 "WFSg"}
"bkHg"
Returns: 2
4)
    
{"eKUNGHktLB",
 "EtBFDndTlG",
 "RRFHmjwrDs",
 "eKYsHlYhlu",
 "ljxyJSwTds",
 "dUQToyWHvl",
 "azDPWRwioE",
 "EARdktoDBh",
 "dmIqcGSvCE",
 "wXypNQEMxz"}
"oDmWcJHGNk"
Returns: 6
5)
    
{"ab",
 "bA"}
"aB"
Returns: -1

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10708

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13908&pm=10708

Writer:

Gluk

Testers:

PabloGilberto , kalinov , ivan_metelsky

Problem categories:

Brute Force