PROBLEM STATEMENT
In the game of Powerball, one player (the "contestant") tries to place a
colored ball into a basket, while the other player (the "gladiator") tries to
prevent the contestant from doing so, usually by slamming his head into the
ground.
The String[] represents a map of the arena in which the game is played. The
String[] will consist of the following characters:
'.' represents open space
'X' represents a wall
'*' represents the basket
The String represents the initial coordinates of the contestant and gladiator.
It will be of the form "<contX> <contY> <gladX> <gladY>", where <contX> and
<contY> are the contestant's initial x and y coordinates, and <gladX> and
<gladY> are the gladiator's initial x and y coordinates. (0,0) is the
upper-left corner of the arena, with x-coordinates increasing to the right and
y-coordinates increasing downwards.
Assume that the contestant and gladiator take turns moving, with the contestant
moving first. Each turn, the contestant/gladiator may move to an adjacent
square (the players may move diagonally), or may decline to move. Neither the
contestant nor the gladiator may exit the arena or move on top of a wall. The
gladiator may not move on top of the basket, and the contestant may not move on
top of the gladiator.
The gladiator wins if the gladiator moves to the same square as the contestant
before the contestant places the ball in the basket (what happens afterwards is
up to your imagination). The contestant scores if he moves to the same square
as the basket before he is caught by the gladiator.
Write a method that determines if either player can win.
- If the contestant has a strategy that always allows him to score, no matter
what moves the gladiator makes, return 1.
- If the gladiator has a strategy that always allows him to catch the
contestant, no matter what moves the contestant makes, return -1.
- If the contestant can avoid the gladiator indefinitely but the gladiator can
prevent the contestant from scoring, return 0.
DEFINITION
Class: Powerball
Method Name: getWinner
Parameters: String[] String
Returns: int
Method signature (be sure your method is public): int getWinner(String[]
arena, String coords);
TopCoder will ensure validity of the inputs. Inputs are valid if all of the
following criteria are met:
* The arena is rectangular; that is, all elements of the String[] have the same
length
* The height of the arena, or the number of elements in the String[], is
between 1 and 10, inclusive
* The width of the arena, or the length of each element of the String[], is
between 1 and 10, inclusive
* The only characters appearing in arena are '.', 'X', and '*'
* There is exactly one basket; that is, the '*' character appears exactly once
in arena
* coords is of the form "<contX> <contY> <gladX> <gladY>", where <contX>,
<contY>, <gladX>, and <gladY> are single digits ('0'-'9'). There is no leading
or trailing whitespace, and a single space separates consecutive tokens
* The initial contestant and gladiator coordinates are within the bounds of the
arena, and they are on top of neither a wall, nor the basket, nor each other
HINT: one approach is to use a graph with O(n^2) vertices, where n is the
number of open spaces in the arena.
EXAMPLES
Suppose arena is
{ "X*" ,
".." }
and coords = "0 1 1 1". Then, if C represents the contestant and G represents
the gladiator, the initial map of the arena is
X*
CG
Since the contestant moves first, he can move diagonally and place the ball in
the basket on his first turn. Return 1.
Next, suppose arena is
{ "X*" ,
".." ,
".." }
and coords = "1 2 0 1". Then a map of the arena is
X*
G.
.C
No matter what the contestant's first move is, the gladiator will be able to
catch him. Return -1.
Finally, suppose arena is
{ ".*." ,
"..." ,
".X." ,
"..." }
and coords = "1 3 1 1".
Then a map of the arena is
.*.
.G.
.X.
.C.
If the gladiator tries to go around the wall in the middle, the contestant can
go around the other side and avoid him. So the gladiator can't catch the
contestant. But the gladiator can keep the contestant from scoring, simply by
sitting in his initial position. Return 0.
More test cases:
Suppose arena is
{ ".X......" ,
"XX......" ,
"........" ,
"...X...." ,
".XX*X..." ,
".X.X...." ,
".XXX...." ,
"........" }
Then:
if coords = "0 7 2 5", return 1 (since the gladiator cannot move through the
basket)
if coords = "2 5 0 7", return 1
if coords = "4 1 5 4", return 1
if coords = "0 0 7 7", return 0
if coords = "0 7 4 3", return 0
if coords = "4 1 4 3", return -1
if arena is
{ ".X.X." ,
".X.X." ,
"....." ,
".XXX." ,
"..*.." ,
"..X.." ,
"..X.." ,
"..X.." ,
"....." }
and coords = "2 0 2 8", return 1