3. В подземелье замка короля Мондрагона, план которого имеет форму прямоугольника 2*N,
хранятся несметные сокровища. Нередкими были попытки злоумышленников пробраться в
подземелье и украсть богатства короля, поэтому он решил поставить в подземелье стражу из
числа солдат регулярной армии. Надо сказать, что личный состав вооруженных сил
королевства имеет отличную военную подготовку, дисциплинирован и стреляет из луков и
арбалетов без промаха. Охране дан был строгий приказ - стрелять во все живое, что они
смогут увидеть. Конечно же, при этом недопустима такая расстановка стражников, при
которой хотя бы один может увидеть другого. Смотреть солдат может в 8 направлениях:
влево, вправо, вперед, назад и по диагоналям как угодно далеко, но, конечно же, только до
стены - сквозь стены солдаты королевства пока еще не научились видеть.
Задание. Напишите    программу    GUARDS,    определяющую    количество    допустимых
расстановок стражи в подземелье. (Заметим, что полное отсутствие стражи в подземелье
также является допустимой расстановкой, поскольку при этом нет стражников, которые
могли бы увидеть других).
Входные данные. В первой строке текстового файла GUABDS.DAT записано количество
тестов. Первая строка каждого теста содержит одно целое число - длину подземелья N
(1<N<30), а вторая и третья - по N чисел из множества {0,1}, определяющих план
подземелья. Значение 0 обозначает свободную клетку, в которую может быть поставлен один
стражник, а значение 1 - клетку, занятую стеной (разумеется, замуровывать солдата в стену
нельзя)
Примечание. В 30% тестов N<=7.
Выходные данные. В текстовый файл GUARDS.SOL выведите для каждого теста в отдельной
строке количество допустимых расстановок стражи.
Пример входных и выходных данных
GUARDS.DAT    GUARDS.SOL
2                        4 
3                        9
1 1 0
0 1 1
3
0 1 0
0 0 0

Грузная задача. И кстати не перебор! А динамика. Хороший перебор набирает где-то 50/100 балов