АВТ
Язык:

Дистанционный практикум по программированию

Задачи Online статус Турниры
Учебники Справка СДО
 
Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь.

1329. 4x4

Ограничение времени: 1 сек.
Ограничение памяти:65536 КБайт
Баллы:100
Статистика Послать на проверку Задачу добавил debug

The 4x4 game is played on a checkered board having 5 rows and 5 columns. The squares are numbered left to right, top to bottom. The squares with numbers 3, 11, 13, 15, and 23 are removed. So, the game board has four 2x2 corner blocks with bridges between them.

There are 16 game pieces on the field, four of each color: red, blue, yellow, and green. Initially, the pieces are placed in the corner blocks (i. e. the squares numbered 8, 12, 14, and 18 are empty).

The objective is to move the pieces so that all the pieces of each color were in the same corner block. A piece may only be moved to an empty square immediately to the right, to the left, above, or below. It is forbidden to move a piece to a square that is occupied by another piece, or to a removed square.

Your task is to write a program that, given the initial game position, will build a sequence of moves leading to the final position with pieces of the same color grouped in the corner blocks.

Note: such a sequence always exists, moreover, it is not unique. Any sequence of no more than 10,000 moves leading to the final position will be considered as a correct solution. The sequence does not have to be optimal.

Limitations

The resulting sequence may not be longer than 10 000 moves.

Input

The input file contains 5 lines of 5 characters each describing the initial position on the game board. The first line represents (left to right) the squares 1, 2, 3, 4, 5; the second line represents the squares 6, 7, 8, 9, 10 and so on. Period characters (“.”) stand for empty fields, “X” for removed fields, and “R”, “B”, “Y” and “G” for pieces of different colors.

Output

The output file should contain a sequence of moves resulting in the final position. Each move is represented on a separate line with two space-delimited integers: the number of the initial square and the number of the destination square.

Example

Input

Output

RRXGG

RG.YG

X.X.X

BR.BY

BBXYY

7 8

9 14

19 18

17 12

8 9

14 19

18 17

12 7

 

 


Статистика Послать на проверку Обсуждение задачи Автор/источник:
Задачи с соревнований / Чемпионат ACM / Рыбинск-2014 /
1328. D - Ingress 1329. 1330. F - Sages 1331. G - Bus Conductor 1332. H - Cryptography
 
время генерации 0.094 сек.
© Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А.