TopCoder problem "WordConnect" used in Delta Round 1 (Division I Level Three)



Problem Statement

    You are given a table of characters. Words are found in table by taking steps up, down, left, or right (up and down refer to row changes, while left and right refer to column changes). The string of letters stepped on during this process is said to be found. If word is found in table, then all of the positions stepped on while finding word are considered pairwise connected. Each occurrence of word that is found is dealt with separately. Connectivity is transitive: if position x connects to y, and position y connects to z, then positions x and z are connected. Return the number of distinct connected components in table (a connected component is a maximal collection of pairwise connected positions). To simplify matters, the characters in word will be distinct.
 

Definition

    
Class:WordConnect
Method:numComponents
Parameters:String, String[]
Returns:int
Method signature:int numComponents(String word, String[] table)
(be sure your method is public)
    
 

Constraints

-word will contain between 1 and 26 lowercase letters ('a'-'z'), inclusive.
-Each character in word will be distinct.
-table will contain between 1 and 50 elements, inclusive.
-Each element of table will contain between 1 and 50 characters, inclusive.
-Each character in table will be a lowercase letter ('a'-'z').
-Each element of table will contain the same number of letters.
 

Examples

0)
    
"top"
{
"toptoptop",
"toptoptop"
}
Returns: 6
There are 6 separate components. Each is numbered below:
111222333 
444555666
1)
    
"top"
{
"aaaaaaaaaaa",
"aaaopopoaaa",
"aaatototaaa",
"aaaopopoaaa",
"aaaaaaaaaaa"
}
Returns: 41
Here there is one large central component, and a surrounding sea of single character components.
2)
    
"topcader"
{
"topcader",
"oaaaaaae",
"paaaaaad",
"caaaaaaa",
"aaaaaaac",
"daaaaaap",
"eaaaaaao",
"redacpot"
}
Returns: 37
A single component lines the outer edge, surrounding a sea of single character components.
3)
    
"topcader"
{
"topcoder",
"oaaaaaae",
"paaaaaad",
"caaaaaaa",
"aaaaaaac",
"daaaaaap",
"eaaaaaao",
"redocpot"
}
Returns: 50
4)
    
"a"
{
"aaaaaaaaaaaaaaaaaaaaaa",
"aaaaaaaaaaaaaaaaaaaaaa",
"aaaaaaaaaaaaaaaaaaaaaa",
"aaaaaaaaaaaaaaaaaaaaaa",
"aaaaaaaaaaaaaaaaaaaaaa",
"aaaaaaaaaaaaaaaaaaaaaa",
"aaaaaaaaaaaaaaaaaaaaaa",
"aaaaaaaaaaaaaaaaaaaaaa",
"aaaaaaaaaaaaaaaaaaaaaa",
"aaaaaaaaaaaaaaaaaaaaaa"
}
Returns: 220

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10706&pm=7495

Writer:

AdminBrett

Testers:

PabloGilberto , Olexiy , Andrew_Lazarev

Problem categories:

Graph Theory