A long long time ago, in the Dreamtime, Australia was a flat grid of rows and columns and each grid cell was land. The rows were numbered to from North to South, and the columns were numbered to from West to East. The cell in row and column was denoted as . One day, the great rainbow serpent rose from the earth at , and moved across Australia, creating rivers wherever it slid. The serpent made consecutive moves, each time moving to the cell directly North (N
), South (S
), East (E
) or West (W
), turning the cell into river. The cell was also turned into river.
Now, millions of years later, you would like to purchase a rectangular block of cells to commemorate the creation of the rivers by the rainbow serpent. You will choose a different colour for each land cell inside your rectangular block. You would like to use as many different colours as possible but insist that every pair of adjacent land cells inside your block share the same colour. Two cells are adjacent if they share an edge. You will not choose a colour for any land cells outside your block, nor will you choose a colour for the river cells inside your block.
Given the moves made by the rainbow serpent, you would like to determine the maximum number of different colours you can choose for land cells in each of rectangular blocks of cells.
Implementation Details
You need to implement the functions init and colours:
init(R, C, sr, sc, M, S)
— The grader will call this function first and exactly once.- and : the number of rows and columns in the grid.
- and : the row and column where the serpent rose from the earth.
- : the number of moves the serpent made.
- : a string of length : is either
N
,S
,E
orW
, denoting that the serpent's move was to the cell immediately North, South, East or West of its current location, for all . You may assume that the serpent never left the grid.
colour(ar, ac, br, bc)
— After callinginit
once, the grader will call this function times in a row.- This function should return a single integer: the maximum number of different colours you can choose for land cells in the rectangular block of cells with North-West corner and South-East corner , according to your rules.
- You may assume that and .
Input Specification
The sample grader reads the input in the following format:
- line 1: four integers , , and ;
- line 2: two integers and ;
- line 3: a string consisting of characters, each
N
,S
,E
orW
(this line should be left blank if ); - lines 4 to : four integers , , and .
Sample Input
6 4 9 4
3 3
NWESSWEWS
2 3 2 3
3 2 4 4
5 3 6 4
1 2 5 3
Sample Output
0
2
1
3
Explanation for Sample Output
Function calls | Return value | Explanation |
---|---|---|
init(6, 4, 3, 3, 9, "NWESSWEWS") |
The module provides your program with the dimensions of the grid, the starting position of the serpent and the moves it made. There is no return value. | |
colour(2, 3, 2, 3) |
The only cell in this rectangle is , which is a river cell. Hence, you cannot choose a colour for any land cells. | |
colour(3,2,4,4) |
The river separates the land cells into two regions: the first region containing the cell , and the second region containing the cells and . Therefore the maximum number of different colours you can choose is . | |
colour(5, 3, 6, 4) |
All the cells in this rectangle are land cells. Since all the land cells are connected, the maximum number of different colours you can choose is . | |
colour(1, 2, 5, 3) |
The river separates the land cells into three regions: the first region containing the cells and , the second region containing the cell and the third region containing the cell . Therefore the maximum number of different colours you can choose is . |
The blue, patterned cells are river cells.
Subtasks
For all subtasks, and .
Subtask | Points | |||
---|---|---|---|---|
Comments
the function
colours
should be namedcolour
andinit
accepts a character array instead of a stringFixed the typo with
colours
. The two function signatures should be