Xếp chỗ học sinh

Điểm: 8,00 (OI)

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

Một lớp học gồm $n$ hàng và $m$ cột, mỗi ô có một học sinh. Hai học sinh được gọi là láng giềng nếu hai ô của họ có cạnh chung.

Học sinh được đánh số từ $1$ đến $n \cdot m$ theo thứ tự dòng: học sinh ở ô tại hàng $i$ , cột $j$ ban đầu mang số $(i - 1) \cdot m + j$ .

Bạn cần tìm một cách xếp chỗ mới — vẫn là một ma trận $n \times m$ chứa đúng các số từ $1$ đến $n \cdot m$ , mỗi số đúng một lần — sao cho không có hai số nào là láng giềng ở cách xếp ban đầu lại tiếp tục là láng giềng ở cách xếp mới. Nếu không tồn tại cách xếp như vậy, hãy báo không có nghiệm.

Dữ liệu vào

Một dòng chứa hai số nguyên $n$ và $m$ .

Dữ liệu ra

Nếu không tồn tại ma trận thoả mãn, in ra một dòng "NO" (không kèm dấu ngoặc kép).

Ngược lại, in ra "YES" ở dòng đầu, rồi $n$ dòng tiếp theo, mỗi dòng có $m$ số nguyên cách nhau bởi dấu cách, tạo thành ma trận thoả yêu cầu.

Nếu có nhiều đáp án thì in ra một đáp án bất kỳ.

Ràng buộc

$1 \leq n, m \leq 10^{5}$
$n \cdot m \leq 10^{5}$

Ví dụ

Input	Output	Giải thích
2 4	YES 5 4 7 2 3 6 1 8	Ma trận ban đầu là 1 2 3 4 / 5 6 7 8. Có thể kiểm tra rằng không có cặp học sinh nào là láng giềng ở cả hai cách xếp.
2 1	NO	Chỉ có hai cách xếp khả dĩ và ở cả hai cách thì học sinh số 1 và số 2 đều là láng giềng.

Bình luận

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