#PU1448. USACO 2024 December Contest, Silver — Problem 3. 2D Conveyor Belt

USACO 2024 December Contest, Silver — Problem 3. 2D Conveyor Belt

USACO 2024 December Contest, Silver — Problem 3. 2D Conveyor Belt

题目描述

Farmer John's milk factory can be described by an NN by NN (1≤N≤10001 \le N \le 1000) grid of cells that contain conveyor belts. Position (a,ba,b) describes the cell that is in the aa-th row from the top and bb-th column from the left. There are 55 types of cells: "L" — the cell is a leftward facing conveyor belt which moves all items on it 1 cell left every time unit. "R" — the cell is a rightward facing conveyor belt which moves all items on it 1 cell right every time unit. "U" — the cell is an upward facing conveyor belt which moves all items on it 1 cell up every time unit. "D" — the cell is a downward facing conveyor belt which moves all items on it 1 cell down every time unit. "?" — Farmer John has not built a conveyor belt at that cell yet.

输入格式

The first line contains NN and QQ. The ii-th of the next QQ lines contains rir_i, cic_i, and tit_i in that order.

输出格式

QQ lines, the ii-th of which describing the minimum number of unusable cells if Farmer John fills optimally builds conveyor belts on all remaining cells that do not currently have a conveyor belt.

数据范围

Inputs 4-5: N≤10N \le 10 Inputs 6-7: N≤40N \le 40 Inputs 8-13: No additional constraints Problem credits: Alex Liang

样例

样例 1

3 5
1 1 R
3 3 L
3 2 D
1 2 L
2 1 U
0
0
0
2
3
The conveyor belt after the fifth day is shown below.
RL?
U??
?DL
One optimal way to build conveyor belts on the remaining cells is as follows.
RLR
URR
LDL
In this configuration, the cells at ($1, 1$), ($1, 2$), and ($2, 1$) are
unusable.

样例 2

3 8
1 1 R
1 2 L
1 3 D
2 3 U
3 3 L
3 2 R
3 1 U
2 1 D
0
2
2
4
4
6
6
9
The conveyor belt after the eighth day is shown below.
RLD
D?U
URL
No matter what conveyor belt Farmer John can build at the center, all cells 
will be unusable.

样例 3

4 13
2 2 R
2 3 R
2 4 D
3 4 D
4 4 L
4 3 L
4 2 U
3 1 D
4 1 R
2 1 L
1 1 D
1 4 L
1 3 D
0
0
0
0
0
0
0
0
11
11
11
11
13

提示

unusable if an item placed at cell cc will never exit the conveyor belt grid (i.e. it will move around in the grid forever). Initially, Farmer John has not started building the factory so all cells start out as "?". For the next QQ (1≤Q≤2⋅1051 \le Q \le 2 \cdot 10^5) days starting from day 11 and ending at day QQ, Farmer John will choose a cell that does not have a conveyor belt and build a conveyor belt at the cell. Specifically, during the ii-th day, Farmer John will build a conveyor belt of type tit_i (ti∈L,R,U,Dt_i \in {\text{{L,R,U,D}}}) at position (ri,cir_i,c_i) (1≤ri,ci≤N1 \le r_i,c_i \le N). It is guaranteed that there is no conveyor belt at position (ri,cir_i,c_i). After each day, help Farmer John find the minimum number of unusable cells he can achieve by optimally building conveyor belts on all remaining cells without a conveyor belt.