Bài 85/2001 - Biến đổi 0 - 1
(Dành cho học sinh THPT)
Cho 2 lưới ô vuông A và B cùng kích thước M xN, mỗi ô có chỉ nhận các giá trị 0 hoặc 1 (A khác B). Các ô
lưới được đánh số từ trên xuống dưới, từ trái qua phải bắt đầu từ 1. Cho phép thực hiện phép biến đổi sau
đây với lưới A:
- Chọn ô (i, j) và đảo giá trị của ô đó và các ô chung cạnh với nó (0 thành 1, 1 thành 0).
Hãy xác định xem bằng cách áp dụng dãy biến đổi trên có thể đưa A về B được hay không? Nếu có hãy chỉ
ra cách sử dụng một số ít nhất phép biến đổi.
Dữ liệu nhập vào từ file văn bản BIENDOI.INP:
- Dòng đầu tiên ghi hai số M, N - kích thước ô lưới (M, N <= 100),
- M dòng tiếp theo, mỗi dòng một xâu N kí tự 0, 1 ứng với dòng tương ứng của A,
- Tiếp theo là một dòng trống,
- M dòng cuối mỗi dòng 1 xâu N kí tự 0, 1 ứng với dòng tương ứng của B.
Dữ liệu ra trong file BIENDOI.OUT:
- Dòng đầu số nguyên k là số lượng phép biến đổi ít nhất cần áp dụng (k = 0 nếu không biến đổi được)
- Dòng thứ i trong số k dòng tiếp theo ghi hai số nguyên xác định ô cần chọn để thực hiện phép biến đổi.
Ví dụ:
BIENDOI. INP
4 5
1 0 0 0 0
0 1 0 0 0
0 0 0 0 0
0 0 1 0 0
BIENDOI.OUT
2
2 1
3 2
Bạn đang xem bài 85/ - 100 DE TIN HSG CO DAP AN
