Здравствуйте!
Недавно решил олимпиадную задачу вот такого содержания. Она называется симпатичные узоры
Условие: Имеется прямоугольник NxM метров. Узор составляется из плиток двух цветов. Необходимо вывести кол-во всех правильных узоров которые можно составить на данном прямоугольнике. Причем узор считается правильным если нигде не встречается квадрата 2х2 метра, полностью покрытого плитками одного цвета.
Входные данные: N и М (1<=MxN<=100)
Вывести кол-во узоров. Узоры получающиеся друг из друга сдвигом поворотом или отражением считаются различными. Время на тест 10 сек.
Примеры выходных данных:
Input.txt Output.txt
2 2 14
3 3 322
Задачу я решил используя размещения с повторениями. Создал матрицу N на М
Делал переборы цифр 1 и 0 (соответсвенно 1 - один цвет допустим белый 0-второй цвет (допустим черный)) а потом проходился по всей матрице , делая поиск квадрата 2 на 2 из одних и тех же цифр
Например пусть N=2 и M=2 . Вот все варианты узоров (ниже я привожу матрицу)
00 00 00 00 01 01 01 01 10 10 10 10 11 11 11 11
00 01 10 11 00 01 10 11 00 01 10 11 00 01 10 11
Здесь всего получилось 16 узоров это по формуле для размещений с повторениями получается (2^N)^M из них 14 правильных, а два крайних неправильно
Аналогично и для других значений . Ответы я сверил все совпадает для 2 на 2 14 узоров для 3 на 3 322 узора
Проблема в том что уже при размерности 5 на 5 получается тест длится около минуты а ведь размерность MxN<=100 так если будет например N=1 и M=100 или даже N=2 и M=50 то компьютер зависнет надолгие часы перебирая все комбинации
Как еще можно решить эту задачу? Перебором получается очень долго

Яростный Меч,

ну да различные...я же все возможные варианты перебираю
ответ сходится но долго

Worobjoff,
Там вначале я писал:
Входные данные: N и М (1<=MxN<=100)
даже если 1х1 то узор считается правильным: либо 0 либо 1, т.е либо первый цвет либо второй
Размерность M и N задается во входном файле

Edd.Dragon,
а ну да плитка 1х1

Вот и ко мне че то никаких идей не приходит каким еще способом можно

Aleksandr Sharahov,
наверняка есть какие нибудь зависимости между комбинациями и вместо того чтобы после очередной генерации комбинации проходится по всей матрице на поиск квадрата одного цвета можно сразу исключить эту комбинацию тем самым время перебора сократится
Например для
00 00 00 00 01 01 01 01 10 10 10 10 11 11 11 11
00 01 10 11 00 01 10 11 00 01 10 11 00 01 10 11
сразу видно что последняя комбинация и первая не подходят и их можно исключить но конечно если размерность побольше тут уж надо как то придумать найти эти зависимости )

Спасибо огромное все ссылки посмотрю
Да перебор действительно убивает большую часть времени

AndreTM,
спасибо большое за книги по ссылкам
я хотел спросить а вот последние две ссылки Динамическое программирование по профилю это просто как отдельная статья или это из какой то книги Если из книги то кто автор и как называется чтобы скачал
Зимняя школа по программированию тоже классная уже скачал