Băng Chuyền 2D

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Farmer John vận hành một nhà máy với lưới $N \times N$ chứa các băng chuyền. Mỗi ô chứa một trong năm loại:

L, R, U, D: băng chuyền di chuyển vật phẩm sang trái, phải, lên, xuống tương ứng
?: ô chưa xây

Một ô được gọi là không sử dụng được nếu vật phẩm đặt tại đó sẽ lặp mãi mãi mà không thoát ra khỏi lưới.

Ban đầu tất cả ô đều là ?. Trong $Q$ ngày, mỗi ngày FJ xây một băng chuyền. Sau mỗi ngày, xác định số ô không sử dụng được tối thiểu có thể đạt được bằng cách điền tối ưu các ô ? còn lại.

Dữ liệu vào

Dòng đầu: hai số nguyên $N$ và $Q$ ( $1 \leq N \leq 1000$ , $1 \leq Q \leq 2 \cdot 10^{5}$ ).
$Q$ dòng tiếp theo: $r_{i}$ , $c_{i}$ , $t_{i}$ (hàng, cột, loại băng chuyền).

Dữ liệu ra

$Q$ dòng, mỗi dòng chứa số ô không sử dụng được tối thiểu sau mỗi ngày.

Ràng buộc

Test $2$ - $4$ : $N \leq 40$
Test $5$ - $13$ : Không có ràng buộc thêm

Ví dụ

Input	Output	Giải thích
3 5 1 1 R 3 3 L 3 2 D 1 2 L 2 1 U	0 0 0 2 3	Sau 5 thao tác, có 3 ô không thể thoát ra ngoài lưới dù điền tối ưu các ô `?`.

Bình luận

Không có bình luận tại thời điểm này.