Bảng nhị phân về 0

Điểm: 4,00 (OI)

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

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

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho bảng nhị phân kích thước $n \times m$ gồm các kí tự 0 và 1.

Trong một thao tác, bạn chọn ba ô khác nhau cùng nằm trong một hình vuông $2 \times 2$ nào đó của bảng, rồi đảo giá trị (0 thành 1, 1 thành 0) trên cả ba ô đó.

Hãy đưa toàn bộ bảng về 0. Bạn được phép thực hiện không quá $3 n m$ thao tác và không cần tối thiểu hoá số thao tác. Có thể chứng minh rằng luôn tồn tại đáp án.

Dữ liệu vào

Dòng đầu chứa số nguyên $t$ — số bộ test.

Với mỗi bộ test:

Dòng đầu chứa hai số nguyên $n, m$ .
$n$ dòng tiếp theo, mỗi dòng là một xâu nhị phân độ dài $m$ mô tả các hàng của bảng.

Dữ liệu ra

Với mỗi bộ test:

Dòng đầu in số nguyên $k$ ( $0 \leq k \leq 3 n m$ ) — số thao tác.
$k$ dòng tiếp theo, mỗi dòng in 6 số nguyên $x_{1}, y_{1}, x_{2}, y_{2}, x_{3}, y_{3}$ ( $1 \leq x_{i} \leq n$ , $1 \leq y_{i} \leq m$ ) mô tả thao tác trên ba ô $(x_{1}, y_{1}), (x_{2}, y_{2}), (x_{3}, y_{3})$ . Ba ô phải khác nhau và cùng thuộc một hình vuông $2 \times 2$ .

Có nhiều đáp án hợp lệ; bất kỳ đáp án nào thoả mãn ràng buộc và đưa được bảng về toàn 0 đều được chấp nhận.

Ràng buộc

$1 \leq t \leq 5000$
$2 \leq n, m \leq 100$
Tổng $n m$ trên tất cả bộ test không vượt quá $20000$ .

Ví dụ

Input	Output	Giải thích
1 2 2 00 00	0	Bảng đã toàn `0`, không cần thao tác.
1 2 2 10 00	3 1 1 2 1 2 2 1 1 1 2 2 2 1 1 2 1 1 2	Một dãy 3 thao tác đưa ô $(1, 1)$ về 0 trong khi các ô khác giữ nguyên. Đáp án không duy nhất.

Bình luận

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