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
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.