0250. Васин сон

Имя входного файла: dream.in
Имя выходного файла: dream.out
Ограничение по времени: 2 s
Ограничение по памяти: 256 megabytes

Однажды Васе приснился очень странный сон. Он был шахматным королем, причем он был не на обычной шахматной доске, а на доске размером 3 *3. Вася не помнит почему, но он должен был обойти всю доску, побывав в каждой клетке ровно один раз и в конце оказаться в начальной клетке. Вася мог сам выбрать клетку, с которой начинал обход, но при этом не мог ходить по диагонали, а только на четыре соседние клетки. Он долго блуждал по доске, но так и не смог ее обойти. Проснувшись, Вася заинтересовался, для каких m и n таким образом можно обойти доску m *n? Он так и не нашел решение этой задачи. Сможете ли Вы решить ее?

Формат входного файла

Во входном файле заданы 2 натуральных числа, разделенных пробелом: m и n - размеры доски. (1 ≤ n ≤ 50, 1 ≤ m ≤ 50, mn > 1).

Формат выходного файла

Если решения Васиной задачи для доски m *n нет, единственная строка выходного файла должна содержать "NO", иначе в первой строке выходного файла выведите "YES" (без кавычек). Далее для каждой клетки доски выведите ее номер в обходе (нумерация начинается с единицы). Таким образом, после "YES" должны следовать m строк по n чисел в каждой, разделенных пробелом. Каждое число от 1 до n *m должно встретиться среди них ровно один раз, и для любых двух соседних чисел клетки с этими числами должны быть соседними. Кроме того, соседними должны быть клетки с числами 1 и n *m

Пример:

dream.indream.out
3 3 NO
2 2 YES 2 3 1 4


Источник: Командное школьное первенство Республики Карелия по программированию, 4 ноября 2007.

Обсудить       Отправить решение



Версия для печати