TopCoder problem "PrinceOfPersia" used in SRM 360 (Division I Level Two)



Problem Statement

    

A maze is a rectangular grid, where each cell is either an empty space or an obstacle. The Prince of Persia is initially positioned in one empty cell, and the Princess is in another one.

Each of them can move from one empty cell to another one only if these cells are adjacent, i. e., share a common side. None of them can appear in a cell with an obstacle.

Their common target is to move into the same cell.

The terrible usurper Jaffar doesn't want that to happen. He is going to put obstacles into some currently empty cells in order to prevent their meeting. He cannot put the obstacles in the cells where the Prince and the Princess are initially located, but he can use any other empty cells.

You will be given a String[] maze containing empty cells ('.'), obstacles ('#') and the initial positions of the Prince and the Princess ('P').

Return the minimum number of obstacles that Jaffar must put to separate the Prince and the Princess. If he is unable to separate them, return -1.

 

Definition

    
Class:PrinceOfPersia
Method:minObstacles
Parameters:String[]
Returns:int
Method signature:int minObstacles(String[] maze)
(be sure your method is public)
    
 

Constraints

-maze will contain between 1 and 10 elements, inclusive.
-Each element of maze will contain between 1 and 10 characters, inclusive.
-Each element of maze will contain the same number of characters.
-Each element of maze will contain only dots ('.'), number signs ('#') and uppercase 'P' characters.
-There will be exactly two 'P' characters in the elements of maze.
 

Examples

0)
    
{"P....",
 "...##",
 "##...",
 "....P"}

Returns: 1
Jaffar will put an obstacle in one of the two central cells of the maze.
1)
    
{".....",
 ".P.P.",
 "....."}
Returns: 3
One of the solutions for Jaffar that uses 3 obstacles is to build a "wall" in the middle column.
2)
    
{".#P.",
 ".P#."}
Returns: 0
The royal persons are already securely separated.
3)
    
{"####",
 "#PP#",
 "####"}
Returns: -1
Remember, Jaffar can't put an obstacle in a cell marked "P".

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10772&pm=7876

Writer:

darnley

Testers:

PabloGilberto , Olexiy , lovro , ivan_metelsky

Problem categories:

Graph Theory, Search