The city of Brisbane has been taken over by large mutated wombats, and you must lead the people to safety.
The roads in Brisbane are laid out in a large grid. There are horizontal roads that run east-to-west, numbered in order from north to south, and vertical roads that run north-to-south, numbered in order from west to east, as shown in the picture below.
The wombats have invaded from the north, and the people are escaping to the south. People can run along horizontal roads in either direction, but on vertical roads they will only run towards the south, towards safety.
The intersection of horizontal road with vertical road is denoted . Each segment of road between two intersections contains some number of wombats, and these numbers may change over time. Your task is to guide each person from some given intersection in the north (on horizontal road ) to some given intersection in the south (on horizontal road ), taking them on a route that passes as few wombats as possible.
To begin, you will be given the size of the grid and the number of wombats on each road segment. Following this you will be given a series of events, each of which is either:
- a change, which alters the number of wombats on some road segment; or
- an escape, where some person arrives at a given intersection on horizontal road , and you must find a route to a given intersection on horizontal road that passes the fewest possible wombats.
You must handle these events by implementing the routines init()
, changeH()
, changeV()
and escape()
, as described below.
Examples
The picture above shows an initial map with horizontal roads and vertical roads, with the number of wombats marked on each segment. Consider the following series of events:
- A person arrives at intersection and wishes to escape to intersection . The smallest number of wombats she can pass is , as indicated by a dashed line.
- Another person arrives at intersection and wishes to escape to intersection . The smallest number of wombats he can pass is , again indicated by a dashed line.
- Two change events occur: the number of wombats on the top segment of vertical road changes to , and the number of wombats on the middle segment of horizontal road changes to . See the circled numbers in the picture below.
- A third person arrives at intersection and wishes to escape to intersection . Now the smallest number of wombats she can pass is , as indicated by the new dashed line.
Procedures
Grader Procedure: init()
Description
This procedure gives you the initial layout of the map, and allows you to initialise any global variables and data structures. It will be called only once, before any calls to
changeH()
,changeV()
orescape()
.
Parameters
R
: The number of horizontal roads.C
: The number of vertical roads.H
: A two-dimensional array of size , where gives the number of wombats on the segment of horizontal road between intersections and .V
: A two-dimensional array of size , where gives the number of wombats on the segment of vertical road between intersections and .
Grader Procedure: changeH()
Description
This procedure will be called when the number of wombats changes on the horizontal road segment between intersections and .
Parameters
P
: Indicates which horizontal road is affected .Q
: Indicates between which two vertical roads the segment lies .W
: The new number of wombats on this road segment .
Grader Procedure: changeV()
Description
This procedure will be called when the number of wombats changes on the vertical road segment between intersections and .
Parameters
P
: Indicates between which two horizontal roads the segment lies .Q
: Indicates which vertical road is affected .W
: The new number of wombats on this road segment .
Grader Function: escape()
Description
This function should calculate the fewest possible wombats a person must pass when travelling from intersection to .
Parameters
V1
: Indicates where the person begins on horizontal row .V2
: Indicates where the person ends on horizontal row .- Returns: The smallest number of wombats the person must pass.
Sample Session
The following session describes the sample above:
Function Call | Returns |
---|---|
init(3, 4, [[0,2,5], [7,1,1], [0,4,0]], [[0,0,0,2], [0,3,4,7]]) | |
escape(2,1) | 2 |
escape(3,3) | 7 |
changeV(0,0,5) | |
changeH(1,1,6) | |
escape(2,1) | 5 |
Input Specification
- line :
- line :
- lines :
- lines :
- line :
- next line:
- next lines: one event per line, in the order in which events occur
If , the empty lines containing the number of wombats on horizontal roads (lines through ) are not necessary.
The line for each event must be in one of the following formats:
- to indicate
changeH
:1 P Q W
- to indicate
changeV
:2 P Q W
- to indicate
escape
:3 V1 V2
Output Specification
For every call of escape
, output an integer on a single line - the smallest number of wombats the person must pass.
Sample Input
3 4
0 2 5
7 1 1
0 4 0
0 0 0 2
0 3 4 7
5
3 2 1
3 3 3
2 0 0 5
1 1 1 6
3 2 1
Sample Output
2
7
5
Constraints
- At most changes (calls to either
changeH()
orchangeV
) - At most calls to
escape()
- At most wombats on any segment at any time
Subtasks
Subtask | Points | Additional Input Constraints |
---|---|---|
1 | 9 | |
2 | 12 | , and there will be no calls to changeH() or changeV() |
3 | 16 | , and there will be at most calls to escape() |
4 | 18 | |
5 | 21 | |
6 | 24 | (None) |
Comments