Bật đèn

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.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

Cho một lưới $N \times N$ phòng, đánh số từ $(1, 1)$ đến $(N, N)$ . Ban đầu chỉ phòng $(1, 1)$ được bật đèn. Bessie bắt đầu tại $(1, 1)$ và chỉ có thể di chuyển sang phòng kề (trên, dưới, trái, phải) nếu phòng đó đã được bật đèn.

Có $M$ công tắc: công tắc ở phòng $(x, y)$ có thể bật đèn phòng $(a, b)$ . Khi Bessie vào một phòng, cô bật tất cả các công tắc trong phòng đó.

Hãy tìm số phòng tối đa Bessie có thể bật đèn.

Dữ liệu vào

Dòng đầu: hai số nguyên $N$ và $M$ .
$M$ dòng tiếp theo: bốn số nguyên $x$ , $y$ , $a$ , $b$ — công tắc ở phòng $(x, y)$ bật đèn phòng $(a, b)$ .

Dữ liệu ra

Một số nguyên duy nhất — số phòng tối đa Bessie có thể bật đèn.

Ràng buộc

$2 \leq N \leq 100$
$1 \leq M \leq 20 000$

Ví dụ

Input	Output	Giải thích
3 6 1 1 1 2 2 1 2 2 1 1 1 3 2 3 3 1 1 3 1 2 1 3 2 1	5	Từ $(1, 1)$ bật đèn $(1, 2)$ và $(1, 3)$ . Đi tới $(1, 3)$ bật đèn $(2, 1)$ . Đi tới $(2, 1)$ bật đèn $(2, 2)$ . Tổng 5 phòng.

Bình luận

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