Connection Status:
Competition Arena > AlphabetPath

AlphabetPath

SRM 523 · 2011-05-25 · by vexorian

SRM 523 · 2011-05-25 · by vexorian · Search, String Manipulation
Class Name: AlphabetPath
Return Type: String
Method Name: doesItExist
Arg Types: (vector<string>)
Problem Statement

Problem Statement

You are given a 2-dimensional matrix of characters represented by the String[] letterMaze. The i-th character of the j-th element of letterMaze represents the character at row i and column j. Each of the 26 letters from 'A' to 'Z' appears exactly once in letterMaze, the remaining characters are periods ('.').

An alphabet path is a sequence of 26 elements of the matrix such that:
  • The first element contains the letter 'A'.
  • The first element and the second element are (horizontally or vertically) adjacent.
  • The second element contains the letter 'B'.
  • The second element and the third element are (horizontally or vertically) adjacent.
  • ...
  • The 25-th element and the 26-th element are (horizontally or vertically) adjacent.
  • The last, 26-th element contains the letter 'Z'.

Given letterMaze return String "YES" if the alphabet path exists in the matrix and "NO" otherwise.

Notes

  • Formally, elements (x1,y1) and (x2,y2) are horizontally or vertically adjacent if and only if abs(x1 - x2) + abs(y1 - y2) = 1.

Constraints

  • letterMaze will contain between 1 and 50 elements, inclusive.
  • Each element of letterMaze will contain between 1 and 50 characters, inclusive.
  • All the elements of letterMaze will contain the same number of characters.
  • Each element of letterMaze will only contain uppercase letters ('A'-'Z') and periods ('.').
  • Each uppercase letter from 'A' to 'Z' will appear exactly once in letterMaze.
Examples
0)
{"ABCDEFGHIJKLMNOPQRSTUVWXYZ"}
Returns: "YES"

Simply go from left to right.

1)
{"ADEHI..Z",
 "BCFGJK.Y",
 ".PONML.X",
 ".QRSTUVW"}
Returns: "YES"
2)
{"ACBDEFGHIJKLMNOPQRSTUVWXYZ"}
Returns: "NO"
3)
{"ABC.......",
 "...DEFGHIJ",
 "TSRQPONMLK",
 "UVWXYZ...."}
Returns: "NO"

The cells marked with C and D are not adjacent, it is impossible to make an alphabet path in this case.

4)
{"..............",
 "..............",
 "..............",
 "...DEFGHIJK...",
 "...C......L...",
 "...B......M...",
 "...A......N...",
 "..........O...",
 "..ZY..TSRQP...",
 "...XWVU.......",
 ".............."}
Returns: "YES"

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

Coding Area

Language: C++17 · define a public class AlphabetPath with a public method string doesItExist(vector<string> letterMaze) · 179 test cases · 2 s / 256 MB per case

Submitting as anonymous