Connection Status:
Competition Arena > AlphabetPaths

AlphabetPaths

SRM 523 · 2011-05-25 · by vexorian

SRM 523 · 2011-05-25 · by vexorian · Brute Force, Simple Search, Iteration
Class Name: AlphabetPaths
Return Type: long
Method Name: count
Arg Types: (vector<string>)
Problem Statement

Problem Statement

The original Latin alphabet contained the following 21 letters:

A B C D E F Z H I K L M N O P Q R S T V X

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 will represent the character at row i and column j. The matrix will contain each of the 21 letters at least once. It may also contain empty cells marked as '.' (quotes for clarity).

A path is a sequence of matrix elements such that the second element is (horizontally or vertically) adjacent to the first one, the third element is adjacent to the second one, and so on. No element may be repeated on a path. A Latin alphabet path is a path consisting of exactly 21 elements, each containing a different letter of the Latin alphabet. The letters are not required to be in any particular order.

Return the total number of Latin alphabet paths in the matrix described by letterMaze.

Notes

  • You may assume that for any valid input the return value fits into a long.
  • Two paths are distinct if for some i their i-th elements have different coordinates. (There may be multiple distinct Latin alphabet paths that contain the letters in the same order.)

Constraints

  • letterMaze will contain between 1 and 21 elements, inclusive.
  • Each element of letterMaze will contain between 1 and 21 characters, inclusive.
  • All elements of letterMaze will contain the same number of characters.
  • Each character in letterMaze will be '.' or an upper case letter from the alphabet described in the statement.
  • Each letter from the Latin alphabet described in the statement will appear at least once in letterMaze.
Examples
0)
{"ABCDEFZHIXKLMNOPQRST",
 "...................V"}
Returns: 2

You can make a valid Latin alphabet path starting at A and going right until reaching the T, then go down to reach V. The opposite path is also a Latin alphabet path.

1)
{"ABCDEFZHIXKLMNOPQRST", "BCDEFZHIXKLMNOPQRSTV", "CDEFZHIXKLMNOPQRSTVA", "DEFZHIXKLMNOPQRSTVAB", "EFZHIXKLMNOPQRSTVABC", "FZHIXKLMNOPQRSTVABCD", "ZHIXKLMNOPQRSTVABCDE", "HIXKLMNOPQRSTVABCDEF", "IXKLMNOPQRSTVABCDEFZ", "XKLMNOPQRSTVABCDEFZH", "KLMNOPQRSTVABCDEFZHI", "LMNOPQRSTVABCDEFZHIX", "MNOPQRSTVABCDEFZHIXK", "NOPQRSTVABCDEFZHIXKL", "OPQRSTVABCDEFZHIXKLM", "PQRSTVABCDEFZHIXKLMN", "QRSTVABCDEFZHIXKLMNO", "RSTVABCDEFZHIXKLMNOP", "STVABCDEFZHIXKLMNOPQ", "TVABCDEFZHIXKLMNOPQR"}
Returns: 199229440
2)
{"ABCABCABCABCABCABCAB", "DEFDEFDEFDEFDEFDEFDE", "ZHIZHIZHIZHIZHIZHIZH", "XKLXKLXKLXKLXKLXKLXK", "MNOMNOMNOMNOMNOMNOMN", "PQRPQRPQRPQRPQRPQRPQ", "STVSTVSTVSTVSTVSTVST", "ABCABCABCABCABCABCAB", "DEFDEFDEFDEFDEFDEFDE", "ZHIZHIZHIZHIZHIZHIZH", "XKLXKLXKLXKLXKLXKLXK", "MNOMNOMNOMNOMNOMNOMN", "PQRPQRPQRPQRPQRPQRPQ", "STVSTVSTVSTVSTVSTVST", "ABCABCABCABCABCABCAB", "DEFDEFDEFDEFDEFDEFDE", "ZHIZHIZHIZHIZHIZHIZH", "XKLXKLXKLXKLXKLXKLXK", "MNOMNOMNOMNOMNOMNOMN", "PQRPQRPQRPQRPQRPQRPQ"}
Returns: 5338808
3)
{"ABCDEFZABCDEFZABCDEF", "HIXKLMNHIXKLMNHIXKLM", "OPQRSTVOPQRSTVOPQRST", "ABCDEFZABCDEFZABCDEF", "HIXKLMNHIXKLMNHIXKLM", "OPQRSTVOPQRSTVOPQRST", "ABCDEFZABCDEFZABCDEF", "HIXKLMNHIXKLMNHIXKLM", "OPQRSTVOPQRSTVOPQRST", "ABCDEFZABCDEFZABCDEF", "HIXKLMNHIXKLMNHIXKLM", "OPQRSTVOPQRSTVOPQRST", "ABCDEFZABCDEFZABCDEF", "HIXKLMNHIXKLMNHIXKLM", "OPQRSTVOPQRSTVOPQRST", "ABCDEFZABCDEFZABCDEF", "HIXKLMNHIXKLMNHIXKLM", "OPQRSTVOPQRSTVOPQRST", "ABCDEFZABCDEFZABCDEF", "HIXKLMNHIXKLMNHIXKLM"}
Returns: 5338808
4)
{"ABCDEABCDEABCDEABCDE", "FZHIXFZHIXFZHIXFZHIX", "KLMNOKLMNOKLMNOKLMNO", "PQRSTPQRSTPQRSTPQRST", "VABCDVABCDVABCDVABCD", "ABCDEABCDEABCDEABCDE", "FZHIXFZHIXFZHIXFZHIX", "KLMNOKLMNOKLMNOKLMNO", "PQRSTPQRSTPQRSTPQRST", "VABCDVABCDVABCDVABCD", "ABCDEABCDEABCDEABCDE", "FZHIXFZHIXFZHIXFZHIX", "KLMNOKLMNOKLMNOKLMNO", "PQRSTPQRSTPQRSTPQRST", "VABCDVABCDVABCDVABCD", "ABCDEABCDEABCDEABCDE", "FZHIXFZHIXFZHIXFZHIX", "KLMNOKLMNOKLMNOKLMNO", "PQRSTPQRSTPQRSTPQRST", "VABCDVABCDVABCDVABCD"}
Returns: 2296264

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

Coding Area

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

Submitting as anonymous