Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |

Поиск в ширину (BFS)

Олимпиадные задачи на английском языке

Олимпиадные задачи на английском языке

22/07/2013 | Лето 2013-14 (командная) (B) |

*Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод*

Послать решение Blockly Посылки Темы Где Обсудить (0)

Mister No (real name Jerry Drake) is a comic book character who frequently gets himself into a lot of
trouble, which he is usually able to get out of. However, this time it's not so ea sy. He was searching for
ancient Mayan treasures and, in the process, stumbled upon a lost temple. Inside the temple there is a
large hall, and inside the hall stands a stone Totem with inscriptions that are the key to understanding
the purpose of life (42). However, getting to the Totem is a great challenge.

The Totem is situated on the opposite side of the hall form the entrance. The floor of the hall is
covered with stone tiles that bear a striking resemblance to domino tiles. Each tile is divided into two
halves (squares), and each half has a number from one to six, inclusive, chiseled into it. Tiles are
arranged in `N` rows, with `N` tiles in each odd-numbered row and `N-1` tiles in each even-numbered
row. The image below corresponds to the first test example (N = 5):

It is only possible to step from one tile to an adjacent one if the two tiles have matching numbers on
halves that share an edge. Help Mister No find the shortest path to the Totem by determining the
sequence of tiles (outputting the sequence of tiles' labels, described below) that need to be stepped on,
in order, from the first to the last tile on the path. If there is no possible path to the Totem, find the
shortest path to the tile with the largest label (so that Mister No can make a heroic jump). The stone
tiles are labelled in row-major order: in the first row, the first tile has the label 1, and the last one N; in
the second row, the first tile is `N+1`, and the last one `2*N-1`, and so on. The entrance leads to the
tile with label 1, and the totem is on the last tile in the last row. Mister No always starts from the
entrance.

The first line of input contains the positive integer `N` (`1\ ≤\ N\ ≤\ 500`), the number of stone tile rows.
Each of the following `N*N-N/2` lines (where “/” stands for integer division) contains two positive
integers `A_i` and `B_i` (`1\ ≤\ A_i,\ B_i\ ≤\ 6`, `1\ ≤\ i\ ≤\ N*N-N/2`), the values chiseled into the left and right
halves, respectively, of tile `i`.

The first line of output must contain the length (in tiles) of the required shortest path.

The second line of output must contain a sequence of space-separated positive integers, the labels of
tiles on the shortest path. As there can exist more than one shortest path, output any one of them.

Sample Input #1

5 1 4 4 5 3 4 5 4 5 2 4 2 5 6 4 4 6 5 2 4 5 1 6 1 1 6 2 3 4 2 5 3 1 2 5 5 4 1 2 2 4 3 2 3 3 4

Sample Output #1

7 1 2 7 12 17 22 23

Sample Input #2

3 1 2 2 3 6 6 2 4 3 5 6 6 4 5 5 6

Sample Output #2

4 1 2 5 8

Sample Input #3

4 1 5 5 3 5 5 5 6 5 3 6 4 4 5 2 5 2 4 4 3 2 4 5 2 1 4 1 6

Sample Output #3

7 1 5 8 12 9 10 13