forked from daiwb/Algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathAlphabetPaths.html
More file actions
21 lines (21 loc) · 4.89 KB
/
AlphabetPaths.html
File metadata and controls
21 lines (21 loc) · 4.89 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
<html><body bgcolor="#cccccc" text="#000000"><table><tr><td colspan="2"><h3>Problem Statement</h3></td></tr><tr><td>    </td><td>The original Latin alphabet contained the following 21 letters: <br></br>
<br></br>
A B C D E F Z H I K L M N O P Q R S T V X<br></br>
<br></br>
You are given a 2-dimensional matrix of characters represented by the vector <string> <b>letterMaze</b>. The i-th character of the j-th element of <b>letterMaze</b> 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).<br></br>
<br></br>
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.<br></br>
<br></br>
Return the total number of Latin alphabet paths in the matrix described by <b>letterMaze</b>.
</td></tr><tr><td colspan="2"><h3>Definition</h3></td></tr><tr><td>    </td><td><table><tr><td>Class:</td><td>AlphabetPaths</td></tr><tr><td>Method:</td><td>count</td></tr><tr><td>Parameters:</td><td>vector <string></td></tr><tr><td>Returns:</td><td>long long</td></tr><tr><td>Method signature:</td><td>long long count(vector <string> letterMaze)</td></tr><tr><td colspan="2">(be sure your method is public)</td></tr></table></td></tr><tr><td>    </td></tr><tr><td></td></tr><tr><td colspan="2"><h3>Notes</h3></td></tr><tr><td align="center" valign="top">-</td><td>You may assume that for any valid input the return value fits into a long long.</td></tr><tr><td align="center" valign="top">-</td><td>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.)</td></tr><tr><td colspan="2"><h3>Constraints</h3></td></tr><tr><td align="center" valign="top">-</td><td><b>letterMaze</b> will contain between 1 and 21 elements, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td>Each element of <b>letterMaze</b> will contain between 1 and 21 characters, inclusive.</td></tr><tr><td align="center" valign="top">-</td><td>All elements of <b>letterMaze</b> will contain the same number of characters.</td></tr><tr><td align="center" valign="top">-</td><td>Each character in <b>letterMaze</b> will be '.' or an upper case letter from the alphabet described in the statement.</td></tr><tr><td align="center" valign="top">-</td><td>Each letter from the Latin alphabet described in the statement will appear at least once in <b>letterMaze</b>.</td></tr><tr><td colspan="2"><h3>Examples</h3></td></tr><tr><td align="center" nowrap="true">0)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{"ABCDEFZHIXKLMNOPQRST",
"...................V"}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 2</pre></td></tr><tr><td><table><tr><td colspan="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.</td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">1)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{".................VT.",
"....................",
"ABCDEFZHIXKLMNOPQRS.",
"..................S.",
".................VT."}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 0</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">2)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{"TBCDE.PQRSA",
"FZHIXKLMNOV"}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 50</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr><tr><td align="center" nowrap="true">3)</td><td></td></tr><tr><td>    </td><td><table><tr><td><table><tr><td><pre>{"ABCDEF.",
"V....Z.",
"T....H.",
"S....I.",
"R....X.",
"KLMNOPQ"}</pre></td></tr></table></td></tr><tr><td><pre>Returns: 4</pre></td></tr><tr><td><table><tr><td colspan="2"></td></tr></table></td></tr></table></td></tr></table><p>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)2003, TopCoder, Inc. All rights reserved. </p></body></html>