TopCoder problem "ABCPath" used in SRM 253 (Division II Level Three)



Problem Statement

    

You will be given a 2-dimensional grid of letters. Write a method to find the length of the longest path of consecutive letters, starting at 'A'. Paths can step from one letter in the grid to any adjacent letter (horizontally, vertically, or diagonally).

For example, in the following grid, there are several paths from 'A' to 'D', but none from 'A' to 'E': 

    { "ABE",
      "CFG",
      "BDH",
      "ABC" }

One such path is: 

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

so, for this grid, your method should return 4.

 

Definition

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

Notes

-The longest path may start at any 'A' character in the input.
 

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').
 

Examples

0)
    
{ "ABE",
  "CFG",
  "BDH",
  "ABC" }
Returns: 4
This is the example from the problem statement.
1)
    
{ "A" }
Returns: 1
2)
    
{ "BCDEFGHIJKLMNOPQRSTUVWXYZ" }
Returns: 0
Paths must start with an 'A'.
3)
    
{ "C",
  "D",
  "B",
  "A" }
Returns: 2
4)
    
{ "KCBVNRXSPVEGUEUFCODMOAXZYWEEWNYAAXRBKGACSLKYRVRKIO",
  "DIMCZDMFLAKUUEPMPGRKXSUUDFYETKYQGQHNFFEXFPXNYEFYEX",
  "DMFRPZCBOWGGHYAPRMXKZPYCSLMWVGMINAVRYUHJKBBRONQEXX",
  "ORGCBHXWMTIKYNLFHYBVHLZFYRPOLLAMBOPMNODWZUBLSQSDZQ",
  "QQXUAIPSCEXZTTINEOFTJDAOBVLXZJLYOQREADUWWSRSSJXDBV",
  "PEDHBZOVMFQQDUCOWVXZELSEBAMBRIKBTJSVMLCAABHAQGBWRP",
  "FUSMGCSCDLYQNIXTSTPJGZKDIAZGHXIOVGAZHYTMIWAIKPMHTJ",
  "QMUEDLXSREWNSMEWWRAUBFANSTOOJGFECBIROYCQTVEYGWPMTU",
  "FFATSKGRQJRIQXGAPLTSXELIHXOPUXIDWZHWNYUMXQEOJIAJDH",
  "LPUTCFHYQIWIYCVOEYHGQGAYRBTRZINKBOJULGYCULRMEOAOFP",
  "YOBMTVIKVJOSGRLKTBHEJPKVYNLJQEWNWARPRMZLDPTAVFIDTE",
  "OOBFZFOXIOZFWNIMLKOTFHGKQAXFCRZHPMPKGZIDFNBGMEAXIJ",
  "VQQFYCNJDQGJPYBVGESDIAJOBOLFPAOVXKPOVODGPFIYGEWITS",
  "AGVBSRLBUYOULWGFOFFYAAONJTLUWRGTYWDIXDXTMDTUYESDPK",
  "AAJOYGCBYTMXQSYSPTBWCSVUMNPRGPOEAVVBGMNHBXCVIQQINJ",
  "SPEDOAHYIDYUJXGLWGVEBGQSNKCURWYDPNXBZCDKVNRVEMRRXC",
  "DVESXKXPJBPSJFSZTGTWGAGCXINUXTICUCWLIBCVYDYUPBUKTS",
  "LPOWAPFNDRJLBUZTHYVFHVUIPOMMPUZFYTVUVDQREFKVWBPQFS",
  "QEASCLDOHJFTWMUODRKVCOTMUJUNNUYXZEPRHYOPUIKNGXYGBF",
  "XQUPBSNYOXBPTLOYUJIHFUICVQNAWFMZAQZLTXKBPIAKXGBHXX" }
Returns: 19
5)
    
{ "EDCCBA",
  "EDCCBA" }
Returns: 3
6)
    
{ "AMNOPA",
  "ALEFQR",
  "KDABGS",
  "AJCHUT",
  "AAIWVA",
  "AZYXAA" }
Returns: 26

Problem url:

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

Problem stats url:

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

Writer:

legakis

Testers:

PabloGilberto , brett1479 , radeye , lars2520 , legakis

Problem categories:

Search