--->
102 задач
<---
Источники
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Как известно, в шахматах горизонтальные строки обозначаются цифрами от 1 до 8, считая от расположения белых фигур, стоящих внизу доски, а вертикальные столбцы – буквами латинского алфавита: A, B, C, D, E, F, G, H.
На шахматной доске в клетке с заданными координатами находиться конь. Сначала делается первый ход конём, а затем – второй ход. Например, для клетки А1 после первого хода возможно перемещение коня на клетку С2 или В3, а после второго хода – на клетки А1, Е1, А3, Е3, В4, D4.
Требуется написать программу, которая определяет координаты всех клеток, куда можно прийти конём за два хода.
Входные данные
В единственной входной строке записано обозначение исходной позиции коня на шахматной доске.
Выходные данные
В единственной строке должны быть записаны через пробел обозначения всех клеток, в которые может переместиться конь после второго хода. Клетки выводятся в следующем порядке: вначале клетки первого ряда слева – направо, далее клетки второго ряда и т.д.
Примеры
Входные данные
A1
Выходные данные
A1 C1 E1 D2 A3 E3 B4 D4 A5 C5
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Для моделирования различных объектов часто применяются так называемые клеточные поля. В простейшем случае – это прямоугольные таблицы, характеризующие некоторую область, а в каждой ячейке таблицы записывается какая-либо информация об исследуемом объекте. В биологии для моделирования распространения вирусов на плоской области в каждой ячейке помечается наличие вируса, а его распространение осуществляется в соседние ячейки по вертикали и горизонтали за одну единицу времени. Некоторые клетки обладают иммунитетом, заразить их невозможно и через них не распространяются вирусы.
Требуется написать программу, которая определяет минимально возможное число вирусов, с помощью которых можно заразить всю исследуемую прямоугольную область (за исключением защищённых клеток).
В приведённом примере таблица имеет размер \(4\times5\), в ней символом "I" помечены защищённые клетки. Видно, что двух вирусов достаточно для заражения всей области. Их можно поместить, например, в клетки, помеченные символом "V".
Входные данные
В первой входной строке записаны два натуральных числа \(M\) и \(N\) - размеры таблицы (количество строк и столбцов соответственно). Известно, что
\(1 \le M, N \le 100\). Во второй строке вначале записано одно число \(K\) - количество защищённых клеток, а далее записаны \(2K\) чисел – координаты этих клеток \(x_i\), \(y_i\) (\(0 \le k \le M \times N, 1 \le x_i \le M, 1 \le y_i \le N\)).
Выходные данные
Программа должна вывести одно число – минимально возможное число вирусов.
Примеры
Входные данные
4 5 3 1 3 2 1 2 2
Выходные данные
2
Выбрано
:
|