Под конец рабочего дня уже соображать трудно - но рискну предложить решение по первой части задачи - так как ни каких дополнительных условий не указанно то максимальная сумма кросворда - это сумма всех чисел - минус сумма чисел не вошедших в кроссворд.
Хотя в моем понимании - кроссворд - это всеже слова.
И не очень понятно, что имеется ввиду под представлением. Если имеется ввиду хранение результатов - то каждая ячейка описывается положением по горизонтали и по вертикали - то есть, как вариант, для ее хранения можно создать структуру, членами которой является позиция по Х У и собственно значение ячейки. А хранить ее можно или в двумерном массиве - самое простое, но не самое эффективное, или использовать два контейнера с уникальным значением ключа. В качестве ключа использовать соответственно в одном случае Х в другом У.
Я бы сделал это так -
Код:
typedef multiset<Struct>Cell;
typedef map<int,multiset<Struct>::iterator>X;
typedef map<int,multiset<Struct>::iterator>Y;
меп ищет по ключу достаточно быстро - решение проблемы, заполнена ли ячейка - поиск по Х или У и т.д. Вобще-то структуру создавать не обязательно - просто так уневерсальней, то есть универсальней я хотел сказать. Все начал заговариваться - пора рулить до хаты.
