C - порядок перемещения в 2D массиве для максимальной собранной суммы

Question

У меня были проблемы с проблемой, что-то вроде этого:

У меня есть 2D-массив, в котором каждая позиция заполнена определенным количеством выборок (представленных в виде целых). Существуют нанороботы, каждый из которых идет по прямой линии через часть линии столбца (каждый с заранее определенным способом), собирая все образцы по пути. Если наноробот собирает образцы в позиции, позиция становится загрязненной, и, если туда приходит другой робот, он запутывается и останавливается. Я могу развернуть роботов в любом порядке, и каждый робот начинает работать только после того, как предыдущий остановился.

С помощью этой информации я хочу найти порядок, в котором собирается наибольшее количество образцов.

Буду признателен за любую помощь в решении этой проблемы, так как я довольно озадачен. У меня есть общее представление о том, как это делается, но я не могу двигаться дальше. Одна вещь определенно состоит в том, как я могу отметить, в каких местах был робот, чтобы я знал, где другие роботы должны остановиться, если они придут, каждое решение, которое я придумаю, кажется очень медленным. Спасибо.

Answer 1

Чтобы помочь вам в разработке ваших алгоритмов, я предоставлю вам возможную структуру данных:

typedef struct LIST {
    int sample;
    struct LIST *next;
} t_list;

typedef struct ITEM {
    t_list *samples;
    int visited;
} t_item;

t_item items[10][10];

Это определяет массив 10х10 элементов. У каждого предмета есть список образцов и указатель того, что он был посещен («загрязнен»). Элемент списка (образец) имеет значение образца и указатель на следующий элемент списка (следующий образец). Надеюсь, это поможет.