printРабочее место участника

printЗадачи

895. Мосты

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Квадратное озеро разделено сеткой на `N`x`N` клеток, в узлах сетки расположены острова. Каждый остров может построить только один мост на соседний (по горизонтали или вертикали) остров или до берега озера (если он также находится по соседству). После завершения строительства мостов с каждого острова должна быть возможность дойти до берега озера и до любого другого острова, переходя с острова на остров по построенным мостам и/или двигаясь по берегу озера. Например, для `N=2` существует 4 варианта строительства мостов с соблюдением условий: с единственного острова можно построить мост вверх, вниз, влево или вправо.
На рисунке показан один из допустимых способов строительства мостов для озера 3x3. Стрелка выходит с острова, построившего соответствующий мост.
Определите количество способов строительства мостов, соблюдая указанные условия, для 1) `N=3`, 2) `N=4` и 3) `N=5`.
В качестве решения необходимо отправить файл, содержащий 3 строки, в каждой строке должно быть одно число. Ответы должны идти в порядке, указанном в задаче. Если какой-либо из ответов неизвестен, укажите вместо него число 0.
Оценка задачи: 5 баллов за каждый правильный ответ.
В качестве решения нужно отправить выходной файл, а не программу!
loading