Lớp Biến Hình

Điểm: 1,00 (OI)

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

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

Input: stdin

Output: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

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

Trong lớp Biến Hình của Giáo sư McGonagall mỗi học sinh nhận được một bảng vật thể gồm $N$ hàng và $M$ cột. Mỗi ô chứa một vật thể ở trạng thái gốc (ký hiệu 0) hoặc trạng thái biến hình (ký hiệu 1).

Giáo sư McGonagall giao cho mỗi học sinh một bảng đích - bảng vật thể mục tiêu mà họ cần đạt được. Để biến đổi bảng, học sinh có thể sử dụng Phép Biến Hình Hàng Loạt: chọn một ô $(r, c)$ bất kỳ, và tất cả vật thể từ ô $(r, c)$ đến ô $(N, M)$ (góc dưới-phải) sẽ đồng thời đảo trạng thái - vật thể ở trạng thái gốc chuyển sang biến hình và ngược lại.

Hãy tìm số phép biến hình ít nhất để biến bảng ban đầu thành bảng đích.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $N$ và $M$ .
$N$ dòng tiếp theo, mỗi dòng chứa một xâu nhị phân độ dài $M$ - mô tả bảng ban đầu $A$ .
$N$ dòng tiếp theo, mỗi dòng chứa một xâu nhị phân độ dài $M$ - mô tả bảng đích $B$ .

Dữ liệu ra

In ra một số nguyên duy nhất - số phép biến hình ít nhất cần thực hiện.

Ràng buộc

$1 \leq N, M \leq 2000$

Ví dụ

Input	Output	Giải thích
3 4 0000 0000 0000 1111 1111 1111	1	Bảng ban đầu toàn `0`, bảng đích toàn `1`. Chỉ cần 1 phép biến hình tại ô $(1, 1)$ - đảo toàn bộ bảng.
3 3 010 101 010 110 110 000	4	Cần 4 phép biến hình để biến bảng ban đầu thành bảng đích.

Bình luận

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