Phản Chiếu

Đ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 có một bức tranh trên lưới $N \times N$ ( $N$ chẵn). Anh ấy tạo bức tranh bằng cách:

Chia lưới thành 4 phần bằng nhau bởi đường ngang và dọc qua tâm.
Vẽ trong phần tư phía trên bên phải.
Phản chiếu bức vẽ qua các đường chia sang 3 phần tư còn lại.

Bessie đã phá hoại bức tranh bằng cách thay đổi trạng thái một số ô (tô thành đã vẽ hoặc xóa). Farmer John muốn khôi phục tính đối xứng phản chiếu với số thao tác ít nhất (mỗi thao tác là tô hoặc xóa một ô).

Sau đó có $U$ cập nhật, mỗi cập nhật đảo trạng thái một ô. Sau mỗi cập nhật, hãy tính lại số thao tác tối thiểu.

Dữ liệu vào

Dòng 1: Hai số nguyên $N$ và $U$ ( $2 \leq N \leq 2000$ , $N$ chẵn, $0 \leq U \leq 10^{5}$ )
$N$ dòng tiếp theo: Mỗi dòng gồm $N$ ký tự, # là ô đã tô, . là ô trống
$U$ dòng tiếp theo: Mỗi dòng gồm hai số nguyên $r$ và $c$ ( $1 \leq r, c \leq N$ ) chỉ ô cần đảo trạng thái

Dữ liệu ra

In ra $U + 1$ dòng, mỗi dòng là số thao tác tối thiểu: dòng đầu tiên trước mọi cập nhật, các dòng sau tương ứng với sau mỗi cập nhật.

Ràng buộc

$2 \leq N \leq 2000$ , $N$ chẵn
$0 \leq U \leq 10^{5}$

Ví dụ

Input	Output	Giải thích
4 5 ..#. ##.# #### ..## 1 3 2 3 4 3 4 4 4 4	4 3 2 1 0 1	Ban đầu cần 4 thao tác. Sau mỗi cập nhật, số thao tác giảm dần đến 0, rồi tăng lại 1 sau cập nhật cuối.

Bình luận

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