| Codeforces Round 270 |
|---|
| Закончено |
Один из источников новых задач — игры. Надо выбрать игру и сосредоточиться на какой-то части механики игры. Так получится неплохая задача.
Давайте попробуем. Puzzle and Dragon стала популярной игрой в Японии — мы сосредоточимся только на части механики игры, в которой нужно передвигать сферы на доске.
Задана доска размера n × m, в каждой ячейке доски находится сфера. Во время игры разрешено совершать следующие ходы. В начале хода вы прикасаетесь к одной из ячеек на доске, затем вы передвигаете палец в одну из соседних ячеек (у ячейки, которая не находится на границе, 8 соседей), затем вы можете еще раз передвинуть палец из текущей ячейки в одну из соседних и так далее. Каждый раз, когда вы двигаете палец от одной ячейки к другой, сферы, находящиеся в этих ячейках, меняются местами. Иными словами, какие бы движения пальцем вы не сделали, сфера в той клетке, к которой вы прикасаетесь, никогда не поменяется.
Задача игрока в игре — достичь такого расположения сфер, при котором сферы пропадут, а герой сможет атаковать врага — но эти детали нам не важны. Мы фокусируемся на другом. Пусть задано начальное расположение сфер, и конечное расположение сфер. Ваша задача — определить, можно ли получить из начального расположения конечное за один ход.
В первой строке записано два целых числа: n и m (1 ≤ n, m ≤ 30) — размеры игровой доски.
В каждой из следующих n строк записано по m целых чисел — описание изначальной доски: j-е число в i-й строке равняется si, j (1 ≤ si, j ≤ 900), где si, j обозначает тип сферы, расположенной в i-м ряду и в j-м столбце игровой доски.
Следующие n строк содержат конечную доску в аналогичном формате. Обратите внимание, что изначальная доска и конечная доска обязательно различаются.
Если решения не существует, выведите: -1.
Если решение существует, то выведите в первой строке целое число k (1 ≤ k ≤ 106) — количество движений пальца в вашем ходе.
В следующей строке выведите два целых числа x0 и y0 (1 ≤ x0 ≤ n; 1 ≤ y0 ≤ m) — положение ячейки, к которой вы прикоснетесь в начале. В каждой из следующих k строк выведите два целых числа xi и yi (1 ≤ xi ≤ n; 1 ≤ yi ≤ m) — ячейка, в которую вы передвигаете палец в данный момент. Обратите внимание, что эта ячейка должна быть соседней с предыдущей, другими словами max(|xi - xi - 1|, |yi - yi - 1|) = 1.
Если у задачи несколько решений, можно вывести любое. Можно доказать, что при указанных ограничениях, если существует решение, то существует и решение с не более, чем 106 операциями.
2 2
1 3
2 3
1 3
3 2
3
1 1
2 2
2 1
1 1
2 2
1 3
2 3
1 2
2 3
-1
1 4
1 2 3 4
4 3 2 1
-1
4 1
1
2
3
4
3
1
2
4
2
3 1
2 1
1 1
