c++ - Getting rid of non-unique entries in an adjacency list -
i'm working on project upper-level c++ class, , building program makes maze, solves it, makes png of said maze. pretty cool stuff. anyways, i'm current on bit need make maze. program makes valid mazes fine, have make each number output unique. output spits out 2 indicies in 2d matrix have walls between them, sample output 3x4 maze follows:
rjeffor1:hydra20 ~/cs302/labs/lab5> ./mazemake 3 4 <- 9:49am
1 2
1 5
2 1
2 3
3 2
5 1
5 9
6 7
7 6
8 9
9 8
9 5
however, last problem need rid of duplicate walls, example 1 2 , 2 1. edit: , mean rid of 2 1, still need wall , therefore 1 2.
here function in attempt fix problem:
void al::make_unique() { vector<int>::iterator it, it0; //need iterate thru last index (int i=0; i<(int)adjlist.size()-1; i++) { (int j=0; j<(int)adjlist.size(); j++) { //find if (i!=j) { it0 = std::find(adjlist[i].begin(), adjlist[i].end(), j); = std::find(adjlist[j].begin(), adjlist[j].end(), i); if (it!=adjlist[j].end() && it!=adjlist[j].end()) //erase if there adjlist[j].erase(it); } } } }
help appreciated, brain done @ point
edit: here how populate adjancency lists, based on indicies directly left right above , below each index
al::al (const int &rows, const int &cols) { adjlist.resize(rows*cols); //run thru , figure out indicies aren't //to fill in adjacency list (int i=0; i<(int)adjlist.size(); i++) { //if not on left edge if (i%cols!=0) adjlist[i].push_back(i-1); //not on right edge if ((i+1)%cols!=0) adjlist[i].push_back(i+1); //not on top edge if (i>=cols) adjlist[i].push_back(i-cols); //not on bottom edge if (i<(rows*cols)-cols) adjlist[i].push_back(i+cols); } }
you remove need post-process , make unique @ end if check adding list. don't add "a b" if "b a" there.
Comments
Post a Comment