Задача A. Лабиринт
Условие
Лабиринт размером N x N клеток задан массивом символов.
Символ '#' обозначеет стену, символ '.' — проход.
Передвигаться по лабиринту можно шагами по горизонтали или вертикали, но не по диагонали.
Требуется найти длину кратчайшего пути между левым верхним и
правым нижнем углами или определить, что пути не существует.
Формат входного файла
Первая строка входного файла содержит размер лабиринта N.
Следующие N строк содержат по N символов — описание лабиринта.
Формат выходного файла
Выходной файл должен содержать единственное целое число — длину кратчайшего пути,
либо −1, если пути не существует
Ограничения
1 ≤
N ≤ 1500, левый верхний угол лабиринта всегда свободен.
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
2
.#
..
|
2
|
| 2 |
2
.#
#.
|
-1
|
Задача B. Квадратное озеро
Условие
Квадратное озеро, покрытое многочисленными мелкими островками,
задается матрицей размером
Nx
N.
Каждый элемент матрицы содержит либо символ '@', обозначающий островок,
либо символ '.' (точка), обозначающий участок свободной воды.
В левом верхнем углу озера находится квадратный плот размером
Mx
M клеток.
За один шаг плот может сдвигаться на одну клетку по горизонтали или вертикали.
Требуется определить минимальное число шагов, необходимых для того,
чтобы плот достиг правого нижнего угла озера.
Формат входного файла
В первой строке входного файла содержатся числа
N и
M,
разделенные пробелами.
В следующих
N строках находится матрица, представляющая озеро,
по
N подряд идущих символов в строке.
Подматрица размером
Mx
M, находящаяся в левом верхнем углу,
не содержит островов (т.е. начальное положение плота всегда допустимо).
Формат выходного файла
Выходной файл должен содержать единственное число - количество необходимых шагов.
Если правого нижнего угла достичь невозможно, то выходной файл должен содержать
число − (минус один).
Ограничения
1 <=
M <=
N <= 100
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
7 2
.......
...@...
.......
..@....
.......
.......
....@..
|
10
|
Problem C. Harder Sokoban Problem
Statement
The game of sokoban is played in a rectangular labirinth of N by N cells
with each cell either empty, denoted by '.' character (ASCII 46),
or occupied by wall, denoted by '#' character (ASCII 35).
There is also a single destination cell, denoted by '*' character (ASCII 42).
One player and one container are located in the empty cells of the labirinth.
The player can move between the empty cells in horizontal or vertical direction.
If the cell where the player tries to move is occupied by container, the container is "pushed"
to the next cell in the same direction. That next cell must, of course, be empty.
The objective of the game is well-known:
to place the container in the destination cell with the minimum number of moves. Your task, however, is different:
given the field, select starting position for the player and the container
so as to maximize the required number of moves.
Input file format
First line of input contains number
N — the field size.
The following
N lines consist of
N characters each — representation the field.
The input field always contains at least one empty cell adjacent to the destination cell.
Output file format
Output file must contain a single integer — the maximal number of moves.
Constraints
2 ≤
N ≤ 25
Sample tests
| No. |
Input file (input.txt) |
Output file (output.txt) |
|---|
| 1 |
2
..
.*
|
0
|
| 2 |
3
..#
...
..*
|
10
|
Задача D. Текстовый редактор
Условие
Начинающий программист Билл написал свою первую программу — текстовый редактор.
Теперь его интересует вопрос, сколько нажатий клавиш потребуется пользователю,
чтобы перевести курсор в любую позицию внутри текста.
Текст, с которым работает редактор Билла, представляет собой набор строк.
Строки состоят из печатных символов (с ASCII-кодами больше 32) и пробелов.
Строка никогда не начинается пробелом и не заканчивается им.
Слово — это часть строки, не содержащая пробелов
и ограниченная слева и справа пробелами или концами строки.
Пользователь может перемещать курсор с помощью восьми операций:
- Влево. Курсор перемещается на один символ влево. Если курсор стоит в начале строки, то он не сдвигается.
- Вправо. Курсор перемещается на один символ вправо. Если курсор стоит в конце строки, то он не сдвигается.
- Вверх. Курсор перемещается на одну строку вверх. Если текущая строка первая, то курсор не сдвигается.
Если после перемещения курсор выходит за пределы строки, то он устанавливается на ее последний символ.
- Вниз. Курсор перемещается на одну строку вниз. Если текущая строка последняя, то курсор не сдвигается.
Если после перемещения курсор выходит за пределы строки, то он устанавливается на ее последний символ.
- В начало строки. Перемещение на первый символ текущей строки.
- В конец строки. Перемещение на последний символ текущей строки.
- На одно слово влево. Если курсор находится внутри слова, то он перемещается на его первый символ.
Если же курсор находится на символе пробела или на первом символе слова, то он перемещается на начало предыдущего слова.
Если текущее слово — первое, то курсор окажется на первом символе строки.
- На одно слово вправо. Курсор перемещается на начало следующего слова. Если текущее слово последнее в строке,
то курсор перемещается на последний символ строки.
Любая операция, кроме двух последних, требует одного нажатия на клавишу.
Перемещение на слово влево и на слово вправо требует двух нажатий (Ctrl+left, Ctrl+right).
Формат входного файла
Первая строка входного файла содержит целые числа
R C — номер текущей строки и номер символа в текущей строке соответственно.
Все остальные строки содержат текст, загруженный в редактор.
Формат выходного файла
Выходной файл должен содержать единственное число:
наименьшее значение
N, такое, что количество нажатий клавиш, необходимое для перевода
из текущей позиции в любую другую позицию текста не превосходит
N.
Ограничения
Размер текста во входном файле не превосходит 2000 байт. Входной файл не содержит пустых строк.
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
3 10
ababaca baca
abcde
ab abc abcde
|
5
|
| 2 |
1 1
begin write(a+b); end.
|
8
|
