TopCoder problem "AlphabetCount" used in SRM 253 (Division I Level Two)



Problem Statement

    

You will be given a 2-dimensional grid of letters and a length. Write a method to count the total number of distinct paths of consecutive letters of the given length, starting at 'A'. Paths can step from one square in the grid to any adjacent square (horizontally, vertically, or diagonally).

For example, in the following grid, there are 7 paths of consecutive letters from 'A' to 'C': 

    { "ABC",
      "CBZ",
      "CZC",
      "BZZ",
      "ZAA" }

    A B C    A . C    A B .    A . .    A . .    A . .    . . .
    . . .    . B .    C . .    C B .    . B .    . B .    . . .
    . . .    . . .    . . .    . . .    C . .    . . C    C . .
    . . .    . . .    . . .    . . .    . . .    . . .    B . .
    . . .    . . .    . . .    . . .    . . .    . . .    . A .
    (spaces are for clarity only)

so, for this grid and a length of 3, your method should return 7.

If there are more than 1,000,000,000 paths, your method should return 1,000,000,000.

 

Definition

    
Class:AlphabetCount
Method:count
Parameters:String[], int
Returns:int
Method signature:int count(String[] grid, int length)
(be sure your method is public)
    
 

Constraints

-grid will contain between 1 and 50 elements, inclusive.
-Each element of grid will be between 1 and 50 characters long, inclusive.
-Each element of grid will have the same length.
-grid will contain only uppercase letters ('A'-'Z').
-length will be between 1 and 26, inclusive.
 

Examples

0)
    
{ "ABC",
  "CBZ",
  "CZC",
  "BZZ",
  "ZAA" }
3
Returns: 7
This is the example from the problem statement.
1)
    
{ "AAAA",
  "AAAA",
  "AAAA" }
1
Returns: 12
2)
    
{ "ABAB",
  "BABA",
  "ABAB",
  "BABA" }
2
Returns: 24
3)
    
{ "HIJKLMNOPQZZZONMLKHIDZYQR",
  "GYXWVUTSRASTZZPSTUJGECPXS",
  "FZABCDEFARQPUQRAAAVWFBOWT",
  "EONMJIHGAJMNOVAAAAAYXANUV",
  "DCBLKDEFIEKLEDWAAAZFGHMLK",
  "UVAZYBCGHFDFCAYXNPQZEDIJA",
  "TSWXAKLZGCZBGZIJOMZRUTCBZ",
  "RQPONMJIHBAZZHZZKLZZSVWXY" }
26
Returns: 7
4)
    
{ "CZC",
  "ZBZ",
  "AZA" }

3
Returns: 4
5)
    
{ "ABCDEFGHIJKLMNOPQRSTUVWXYZ",
  "ABCDEFGHIJKLMNOPQRSTUVWXYZ",
  "ABCDEFGHIJKLMNOPQRSTUVWXYZ" }
26
Returns: 1000000000
6)
    
{ "BDBCBACABDDCCADCBDDCBDDDBCCCCABACADDDCCCBADDDBADCA",
  "DCBBBACBDBACCADABCCAABACDBADBCBBABACBCADADCBDABBBD" }

4
Returns: 20

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=7227&pm=4668

Writer:

legakis

Testers:

PabloGilberto , lbackstrom , brett1479 , radeye

Problem categories:

Dynamic Programming