Connection Status:
Competition Arena > WordsGame

WordsGame

SRM 454 · 2009-12-05 · by Gluk

SRM 454 · 2009-12-05 · by Gluk · Brute Force
Class Name: WordsGame
Return Type: int
Method Name: minimumSwaps
Arg Types: (vector<string>, string)
Problem Statement

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.

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)
{"sDQmQnoMGj","YafplwbBRW","fVwRishQWO","yUusOqnoCr","rAXFEfVTnS","hjVSUSWmda","PTGIcJTKqo","bQEDeeqcYC","nFolORcRKh","oXQtzHuZLW"}
"WuoDdJZbRM"
Returns: -1
2)
{"TAfrjRZ","toAXqro","dqgqWtu","JpWketB","lULWPip","kPIDwAd","WOjyQbb"}
"xempfPT"
Returns: -1
3)
{"GrzCmw","NTgqEn","iqPnBA","PvsYQd","BawoPg","ypmeTu"}
"iJkofN"
Returns: -1
4)
{"hJaEzo","WdrJkk","NbdOyb","MrjSPT","kvwbVX","mQCBPj"}
"ETyAWi"
Returns: -1
100)
{"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.

101)
{"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.

Submissions are judged against all 120 archived test cases, of which 7 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class WordsGame with a public method int minimumSwaps(vector<string> grid, string word) · 120 test cases · 2 s / 256 MB per case

Submitting as anonymous