15844번 - Land of the Rainbow Gold 서브태스크다국어언어 제한함수 구현

A long long time ago, in the Dreamtime, Australia was a flat grid of R rows and C columns and each grid cell was land. The rows were numbered 1 to R from North to South, and the columns were numbered 1 to C from West to East. The cell in row r and column c was denoted as (r, c). One day, the great rainbow serpent rose from the earth at (s_r, s_c), and moved across Australia, creating rivers wherever it slid. The serpent made M 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 (s_r, s_c) 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 Q rectangular blocks of cells.

• 0 ≤ M ≤ 100,000
• R, C, Q ≥ 1

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.
  • R and C: the number of rows and columns in the grid.
  • sr and sc: the row and column where the serpent rose from the earth.
  • M: the number of moves the serpent made.
  • S: a string of length M: S[i] is either N, S, E or W, denoting that the serpent's ith move was to the cell immediately North, South, East or West of its current location, for all 0 ≤ i ≤ M - 1. You may assume that the serpent never left the grid.
• colours(ar, ac, br, bc) --- After calling init once, the grader will call this function Q 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 (a_r, a_c) and South-East corner (b_r, b_c), according to your rules.
  • You may assume that 1 ≤ a_r ≤ b_r ≤ R and 1 ≤ a_c ≤ b_c ≤ C.

Please consult the provided template files for further details on implementing a solution specific to your programming language.

The sample grader reads the input in the following format:

• line 1: four integers R, C, M and Q;
• line 2: two integers sr and sc;
• line 3: a string S consisting of M characters, each N, S, E or W (this line should be left blank if M = 0);
• lines 4 to Q + 3: four integers a_r, a_c, b_r and b_c.

The following diagrams correspond to the sample session above. The blue, patterned cells are river cells.

예제 입력

6 4 9 4
3 3
NWESSWEWS
2 3 2 3
3 2 4 4
5 3 6 4
1 2 5 3

예제 출력

0
2
1
3

Feedback for this sample testcase will be provided as "Sample Data" upon submission.

• R ≤ 50
• C ≤ 50
• Q ≤ 1,000

• R = 2
• C ≤ 200,000
• Q ≤ 100,000

• R ≤ 200,000
• C ≤ 200,000
• Q = 1

• R ≤ 1,000
• C ≤ 1,000
• Q ≤ 100,000

• R ≤ 200,000
• C ≤ 200,000
• Q ≤ 100,000

• public.zip