Want to try solving this problem? You can submit your code online if you log in or register.
It is World Youth Day 2008, and you have joined the masses in Sydney flocking to see the Pope. The crowds are enormous, and you decide there is only one way that you will be able to meet His Holiness to obtain an autograph: crowd surfing.
The stadium is a large rectangle with the Pope standing in the south-east corner. Your hope is the crowd will carry you above their heads from where you are standing all the way across to the Pope. Unfortunately the crowd is not very organised--some sections of the crowd will carry you south, some sections will carry you east, and some sections are so disorganised that they will just drop you back onto the ground.
As an example, consider the map above, where the stadium is broken into a 4 x 5 grid of squares. The arrows show the direction in which the crowd will carry you from each square, and the stars indicate squares in which the crowd will drop you.
Suppose you begin in the top left square. The crowd will carry you south, then east, then south, then three squares east, then south again to where the Pope is standing. On the other hand, suppose you begin in the bottom left square. In this case, the crowd will carry you two squares east and then drop you.
Your task is to decide how many starting points are bad, i.e., will lead you to being dropped. For the example above, there are eight bad starting points; these are indicated with crosses in the diagram below.
The input will describe the stadium as a grid of squares, and will show how the crowd moves you from each square.
The first line of input will consist of two integers r and c, separated by a single space. These indicate that the stadium is broken into a grid with r rows and c columns ( 1 <= r,c <= 1000). Following this will be r lines (ordered from north to south), each containing c characters (ordered from west to east), describing the individual squares within the stadium.
Each square of the grid will be described by one of the characters `v', `>', `*', or `+':
Your output file must consist of a single integer giving the number of bad squares, i.e., the number of squares that lead to you being dropped.
4 5 v*v>v >v>*v v>>>v >>*>+
3 4 >>vv >>>v >>*+
The first example input and output files correspond to the example discussed above. In the second example, every square along the bottom row is bad (except for where the Pope is standing), and all other squares are good; therefore the answer is 3.
The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.
© Australian Mathematics Trust 2001-2023
Page generated: 24 March 2023, 8:49pm AEDT