Oh, so you want to start at a given Point at get all points around this one, right?
But you still want to figure out the number of combinations right?
Ah and also note that there is a closing bracked missing after your makePoint function...
Furthermore, calling your function from main() everything is fine, all points are marked as untouched.
Then within your function you set a point to visited, and never unset the "touched" variable to false, so as soon as a button is visited it never gets untouched (which makes recursive things useless because they won't be recalculated)
try adding p->touched = false; at the end of the function. i think that might actually do the trick, if it doesnt, continue reading ...
(I'm sorry, i don't find the right words to explain that)
I'll use make some changes to use std::vector instead of array and var with length of the array and i'll simulate your pointer behaviour by a function definition with call-by-reference
1 2 3 4 5
|
struct point {
bool touched;
unsigned int number; // Not used anywhere
std::vector<unsigned short> rlist;
}
| |
Now I'll give it an other try with that many constraints...
but I'll just try to get the Function getRoutes to work, everything else seems fine to me.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120
|
#include <iostream>
#include <vector>
struct point {
bool touched;
unsigned int number; /// Not needed anywhere
std::vector<unsigned short> rlist;
};
point makePoint(unsigned short num){
point p;
p.touched = false;
switch ( num ){
case 0:
p.rlist.push_back(1);
p.rlist.push_back(3);
p.rlist.push_back(4);
break;
case 1:
p.rlist.push_back(0);
p.rlist.push_back(2);
p.rlist.push_back(3);
p.rlist.push_back(4);
p.rlist.push_back(5);
break;
case 2:
p.rlist.push_back(1);
p.rlist.push_back(4);
p.rlist.push_back(5);
break;
case 3:
p.rlist.push_back(0);
p.rlist.push_back(1);
p.rlist.push_back(3);
p.rlist.push_back(6);
p.rlist.push_back(7);
break;
case 4:
p.rlist.push_back(0);
p.rlist.push_back(1);
p.rlist.push_back(2);
p.rlist.push_back(3);
p.rlist.push_back(4);
p.rlist.push_back(5);
p.rlist.push_back(6);
p.rlist.push_back(7);
p.rlist.push_back(8);
break;
case 5:
p.rlist.push_back(1);
p.rlist.push_back(2);
p.rlist.push_back(4);
p.rlist.push_back(7);
p.rlist.push_back(8);
break;
case 6:
p.rlist.push_back(3);
p.rlist.push_back(4);
p.rlist.push_back(7);
break;
case 7:
p.rlist.push_back(3);
p.rlist.push_back(4);
p.rlist.push_back(5);
p.rlist.push_back(6);
p.rlist.push_back(8);
break;
case 8:
p.rlist.push_back(4);
p.rlist.push_back(5);
p.rlist.push_back(7);
break;
default:
break;
}
return p;
}
int GetCombinations(int start, std::vector<point> points)
{
points[start].touched = true;
int combinations = 0;
/// Loop through Connected points
for(int i = 0; i < points[start].rlist.size(); i++)
{
/// Check if a connected point is touched (Note: looping through points[start].rlist
/// makes it mandatory to call it so ugly because:
/// First i = points[start].rlist[0], the first connected point and so on
if(points[points[start].rlist[i]].touched == false)
{
combinations += 1; // When a Point is not touched yet, increase counter by 1
// look for all combinations with that points that are not touched
combinations += GetCombinations(points[start].rlist[i], points);
}
}
points[start].touched = false; // DO NOT FORGET THAT, otherwise you will get "8" as result
return combinations;
}
void GetCombinations(std::vector<point> points)
{
int combinations = 0;
/// Look for the sum of the combinations from each starting position
for(int i = 0; i < points.size(); i++)
combinations += GetCombinations(i, points);
std::cout << "Possible Combinations: " << combinations << std::endl;
}
int main(void)
{
std::vector<point> Points;
for( unsigned short i=0; i < 9; i++)
Points.push_back(makePoint(i));
GetCombinations(Points);
return 0;
}
| |
ps. sorry for the formatting, I made the code in QtCreator and copied it but the taps are for some reason converted to 8 spaces