Цитата(Vicipi @ 20.2.2008, 21:45  ) |
| ему трудно будет доказать это |
Еще бы. Доска 6*6 с одной вырезанной клеткой состоит из 35 клеток, и замостить ее трехклеточными фигурами весьма проблематично.
Фтопку.
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Центр помощи > [Алгоритм] двумерный массив уголков |
| Автор: Vicipi 20.2.2008, 20:45 |
| Влас и Еник играют в шахматы. Когда им это надоедает, Влас спорит с Еником, что он может замостить шахматную доску фигурами в форме уголка. Еник знает, что это невозможно, и говорит, что может замостить такими фигурами шаматнную доску с вырезанной верхней правой клектой. Тогда Влас, не подумавши, говорит, что он может замостить вообще любую доску размера 2nx2n без одной произвольной вырезанной клетки. Но он чувствует, что самому ему трудно будет доказать это, помогите ему. Входные данные: В первой строке – число n (0<n<10). Во второй строке - координаты вырезанной клетки. Выходные данные: 2n строк по 2n чисел в каждой через пробел – схема замощения доски. Клетки, покрытые i-ым уголком, должны сожержать число i. Уголки нумеруются с 1 до (2n*2n-1)/3. На месте вырезанной клетки должен стоять 0. Если невозможно замостить доску, вывести «-1». Пример входных данных: 2 2 1 Пример выходных данных: 1 1 2 2 0 1 3 2 4 3 3 5 4 4 5 5 Я не пойму алгоритма заполнения массива. Как решить эту задачу? И как в самом начале задать этот массив(я не знаю как динамические создаются)? |
| Автор: Akina 20.2.2008, 21:36 | ||
Еще бы. Доска 6*6 с одной вырезанной клеткой состоит из 35 клеток, и замостить ее трехклеточными фигурами весьма проблематично. Фтопку. |
| Автор: PPS05 21.2.2008, 21:16 | ||
2^n строк по 2^n чисел. Зачача решается рекурсивным делением на 4 квадрата: расположим уголок так, чтобы в каждом из четырех квадратов была 1 занятая клетка (или дырка). Дальше решаем такую же задачу для каждого из 4 квадратов. |
| Автор: Vicipi 21.2.2008, 22:05 |
| PPS05, спасибо, я подумаю над этим!!!!!!!! |