Connection Status:
Competition Arena > AlphabetCount

AlphabetCount

SRM 253 · 2005-07-23 · by legakis

SRM 253 · 2005-07-23 · by legakis · Dynamic Programming
Class Name: AlphabetCount
Return Type: int
Method Name: count
Arg Types: (vector<string>, int)
Problem Statement

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.

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)
{ "ABCDEFGHIJKLMNOPQRSTUVWXY",
  "ZZZZZZZZZZZZAAAAAAAAAAAAZ",
  "ABCDEFGHIJKLMNOPQRSTUVWXY",
  "ZZZZZZZZZZZZAAAAAAAAAAAAA",
  "ABCDEFGHIJKLMNOPQRSTUVWXY" }
26
Returns: 2

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

Coding Area

Language: C++17 · define a public class AlphabetCount with a public method int count(vector<string> grid, int length) · 63 test cases · 2 s / 256 MB per case

Submitting as anonymous