二维数组中最大采集和的 c 阶运动

Question

I've been having trouble with a problem, something like this:

I have a 2D array where each position is filled with a certain number samples (represented by ints). There are nanorobots, each going in a straight line through a part of a line of column (each with a pre-specified way), collecting all samples along the way. If a nanorobot collects samples on a position, the position becomes contaminated and if another robot comes there, it gets confused and stops. I can deploy the robots in any order, and each robot starts working only after the previous one has stopped.

With this information, I want to find the order in which the highest number of samples is collected.

Any help with the problem would be appreciated, as I am pretty stumped. I have a general idea of how it's done, but can't seem to move forward. One thing specifically is how do I mark which places a robot has been to so that i know where other robots should stop if they come there, every solution I've come up with seems really slow. Thanks.

转载于:https://stackoverflow.com/questions/53249237/c-order-of-movement-in-a-2d-array-for-maximum-sum-collected

Answer 1

To help you developing your algorithms, I provide you with a possible data structure:

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];

This defines an array of 10x10 items. Each item has a list of samples and an indicator that it has been visited ("contaminated"). A list element (a sample) has the sample value and a pointer to the next list element (the next sample). I hope this helps.