TopCoder problem "FourBears" used in SRM 303 (Division I Level Three)



Problem Statement

    

An earthquake took place yesterday and caused some of the passages in the cave to be obstructed by stones. There are four bears trapped in the cave and they want to reach each other. You have to determine the minimum number of passages that must be cleared to allow each bear to reach all the other bears.

The cave is represented as a rectangular field. Each cell in the field corresponds to a passage. Obstructed passages are denoted by '.' symbols and unobstructed passages are denoted by 'X' symbols. Bears can only move in four directions: left, right, up and down; they can't leave the field and can't walk through obstructed passages.

The first two bears are located in the first column of field and are denoted by 'B' symbols. All other cells in the first column are obstructed passages. You are NOT allowed to clear any obstructed passages in that column.

The last two bears are located in the last column of field and are denoted by 'B' symbols. All other cells in the last column are obstructed passages. You are NOT allowed to clear any obstructed passages in that column.

You will be given the cave as a rectangular field, each element of which represents a row of the cave. Your method should return the minimum number of passages that must be cleared to allow each bear to reach all the other bears.

 

Definition

    
Class:FourBears
Method:clearPassages
Parameters:String[]
Returns:int
Method signature:int clearPassages(String[] field)
(be sure your method is public)
    
 

Constraints

- field will have between 2 and 7 elements, inclusive.
- All elements in field will have the same length between 3 and 50, inclusive.
- The first column in field will have exactly two 'B' symbols denoting the bears, all other symbols will be '.' in that column.
- The last column in field will have exactly two 'B' symbols denoting the bears, all other symbols will be '.' in that column.
- All columns except the first and the last will contain only '.' and 'X' symbols.
 

Examples

0)
    
{
 "B.X...............",
 "..X..XXXXXXXXXX..B",
 "B.X..X........X...",
 ".....X........X...",
 "..XXXX........X..B"
}
Returns: 7
The passages which must be cleared are marked with '#' characters. 
 B#X...............
 ..X..XXXXXXXXXX##B
 B#X..X........X...
 ..#..X........X...
 ..XXXX........X##B
1)
    
{
 "..................",
 "B..........XXXX..B",
 "..........X.......",
 "....XXXXXX........",
 "..........XX......",
 "B............XX..B",
 ".................."
}
Returns: 15
 ..................
 B#........#XXXX##B
 .#........X.......
 .###XXXXXX#.......
 .#........XX......
 B#.........##XX##B
 ..................
2)
    
{
 "B.B",
 "...",
 "B.B"
}
Returns: 3
 B#B
 .#.
 B#B
3)
    
{
 "..B",
 "B.B",
 "B.."
}
Returns: 1
 ..B
 B#B
 B..
4)
    
{
 "B..................XX.................XX.XXX.....B",
 "...XXXXX.....XXXX......XXXXX.....XXXX..XXX.XXXX...",
 "............XX..................XX................",
 ".......XXX........XX..X....XXX...........XXX......",
 "............XXX......X.XXX......XXX.XXX..X.XXX....",
 "....XXXX......XXX...X...XXXX......XXX.XXXX........",
 "B..XX..............XX............................B"
}
Returns: 28

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9824&pm=6062

Writer:

Snail

Testers:

PabloGilberto , brett1479 , Yarin , vorthys , Olexiy

Problem categories:

Brute Force, Dynamic Programming, Search