Задача A. Лабиринт
Условие
Лабиринт задан как двумерный массив символов '.' и '#', означающих пустое пространство и стену соответственно.
В любой не занятой стеной клетке может находиться Искатель. Ему разрешено перемещаться по клеткам лабиринта в четырех направлениях: вверх,
вниз, влево и вправо. Покидать лабиринт через внешнюю границу запрещено, ибо за его пределами находится сплошная стена. Требуется написать
программу, которая по заданному лабиринту определяет существует ли путь от входа к выходу.
Формат входного файла
Первая строка входного файла содержит числа
N и
M - количества строк и столбцов в описании лабиринта соответственно.
В следующих
N строках содержатся по
M символов из множества '.' (пустое пространство) , '#' (стена), 'S' (вход), 'F' (выход).
В описании лабиринта присутствует ровно один символ 'S' и ровно один 'F'.
Формат выходного файла
Выведите в выходной файл текстовую строку 'YES', если существует путь от входа к выходу и 'NO' в противном случае.
Ограничения
1 ≤ N,M ≤ 1000
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
3 3
S#.
.#F
...
|
YES
|
| 2 |
3 3
S#.
.#F
#..
|
NO
|
Задача B. Слово из кубиков
Условие
Имеется
N кубиков, на гранях которых написаны буквы.
Требуется определить, можно ли из этих кубиков составить данное слово длиной
K символов,
и если да, то вывести номера использованных кубиков.
При этом каждый кубик можно использовать только один раз.
Если решений несколько, выдать любое из них.
Формат входного файла
В первой строке входного файла содержится количество кубиков
N.
Во второй строке — слово, в следующих
N строках — по шесть символов без разделителей,
определяющих буквы на гранях кубиков. (Порядок букв не имеет значения).
Формат выходного файла
Выходной файл должен содержать последовательность из
K различных целых чисел от
1 до
N,
задающих номера кубиков для каждой буквы слова, начиная с первой.
Если решения нет, выходной файл должен содержать единственное число 0.
Ограничения
1 ≤ N, K ≤ 12.
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
5
TEST
ABCDAB
TTTTTT
STSTST
CREATE
ERRORS
|
2 5 3 4
|
Задача C. Обход доски конем
Условие
Напишите программу, которая по заданным размерам прямоугольного участка шахматной доски определяет такую последовательность ходов конем,
что каждая клетка участка оказывается посещенной ровно один раз. При этом начинать обход можно с любой клетки. Конь ходит согласно обычным шахматным
правилам, смещаясь на две клетки по одному из направлений и на одну по другому. По горизонтали клетки нумеруются заглавными буквами латинского алфавита,
по вертикали — цифрами.
Формат входного файла
Первая строка входного файла содержит целые положительные числа
N и
M — ширина и высота участка шахматной доски соответственно.
Формат выходного файла
Выведите в выходной файл текстовую строку — последовательность клеток в том порядке в котором их должен пройти конь. Каждая клетка должна присутствовать
в ответе ровно один раз. Каждый элемент, задающий позицию должен состоять из буквы латинского алфавита и цифры. Соседние элементы разделяются пробелами.
Если решения не существует, выведите "No solution".
Ограничения
1 ≤ N * M ≤ 30
Примеры тестов
| № |
Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|
| 1 |
1 1
|
A1
|
| 2 |
1 2
|
No solution
|
| 3 |
3 4
|
A1 B3 C1 A2 B4 C2 A3 B1 C3 A4 B2 C4
|
