TopCoder problem "Trekking" used in SRM 345 (Division II Level One)



Problem Statement

    

You are planning a small trek over at the local mountain range. It will involve walking for several days and spending the nights in a tent. The mountains are not very friendly (they're steep and rocky), and therefore many locations are not suitable for setting up a camp. You will be given a String trail which represents the locations in the order in which you are visiting them. trail[i] is '.' if it's possible to camp at the i-th location, and '^' otherwise.

You have several alternative plans to follow, given in the String[] plans. plans[i][j] is lowercase 'w' if according to the i-th plan you are going to walk through location j, and uppercase 'C' if you are going to camp there. A plan is invalid if it involves camping at a location that's not suitable for it.

Given trail and plans return the minimum number of nights that must be spent in the mountains, according to one of the valid plans. If all plans are invalid, return -1

 

Definition

    
Class:Trekking
Method:findCamps
Parameters:String, String[]
Returns:int
Method signature:int findCamps(String trail, String[] plans)
(be sure your method is public)
    
 

Constraints

-trail will contain between 2 and 50 characters, inclusive.
-trail will contain only the characters '.' and '^'.
-plans will contain between 2 and 50 elements, inclusive.
-Each element of plans will contain the same number of characters as trail.
-Each element of plans will contain only the characters 'w' and 'C'.
 

Examples

0)
    
"^^....^^^..."
{"CwwCwwCwwCww",
 "wwwCwCwwwCww",
 "wwwwCwwwwCww"}
Returns: 2
The first plan is not valid because it involves camping in the first visited location, which is not suitable for camping. The other two plans are valid, but the third involves only two camps, so it's the best one.
1)
    
"^^^^"
{"wwww",
 "wwwC"
}
Returns: 0
2)
    
"^^.^^^^"
{"wwCwwwC",
 "wwwCwww",
 "wCwwwCw"}
Returns: -1
3)
    
"^^^^....^.^.^."
{"wwwwCwwwwCwCwC",
 "wwwwCwwCwCwwwC",
 "wwwCwwwCwwwCww",
 "wwwwwCwwwCwwwC"}
Returns: 3
4)
    
".............."
{"CwCwCwCwCwCwCw",
 "CwwCwwCwwCwwCw"}
Returns: 5

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10669&pm=7650

Writer:

rusolis

Testers:

PabloGilberto , brett1479 , Olexiy , ged

Problem categories:

Simple Search, Iteration, String Manipulation