поэтому я только что прошел краткий курс программирования ограничений, и первый тест — написать программу для:
Цель: найти назначения цветов зон s.t. нет
две смежные зоны окрашены в один цвет (изображение вставлено)
это код cpp, который я придумал, чтобы решить проблему, но, к сожалению, он не решает проблему, я запустил код через отладчик, но я понял, как это вызов, чтобы отлаживать рекурсивные коды .. кто-то может взглянуть и Помоги мне?
#include <iostream>
#include <vector>
#include <string>
#include <stdio.h>enum Colours{red,green,blue,yellow};
static int count = 0;
class Zones
{
int side1;
int side2;
int side3;
int side4;
Colours colour;
public : std::vector<int> sides;
public : std::string name;
public :
Zones(){}
Zones(int s1, int s2, int s3, int s4, std::string nm)
{
side1=s1;
side2=s2;
side3=s3;
side4=s4;
sides.push_back(s1);
sides.push_back(s2);
sides.push_back(s3);
sides.push_back(s4);
name= nm;
}
Zones(int s1, int s2, int s3, std::string nm)
{
side1=s1;
side2=s2;
side3=s3;
sides.push_back(s1);
sides.push_back(s2);
sides.push_back(s3);
name= nm;
}
void setZoneColour(Colours colour)
{
this->colour = colour;
}
Colours getZoneColour()
{
return this->colour;
}
};
void mapColouring( std::vector<Colours>colVec, std::vector<Zones> zSolVec, std::vector<Zones> zVec);
int main(int argc, char **argv)
{
Zones z1(2,3,4,5,"z1");
Zones z2(1,3,4,5,"z2");
Zones z3(1,2,4,"z3");
Zones z4(1,2,3,5,"z4");
Zones z5(1,2,4,"z5");
std::vector<Zones> solVec;
std::vector<Zones> zVec;
zVec.push_back(z1);
zVec.push_back(z2);
zVec.push_back(z3);
zVec.push_back(z4);
zVec.push_back(z5);
std::vector<Colours> shades;
shades.push_back(red);
shades.push_back(green);
shades.push_back(blue);
shades.push_back(yellow);
mapColouring(shades,solVec,zVec);
return 0;
}
void mapColouring( std::vector<Colours>colVec, std::vector<Zones> zSolVec, std::vector<Zones> zVec)
{
if(zSolVec.capacity() == 5)
{
//possible solution found, print it
count++;
//std::cout<<"we got here\n";
std::cout<<std::endl<<count<<")";
for(Zones z : zSolVec)
{
std::cout<<z.name<<"-"<<z.getZoneColour()<<" ";
}
}
else
{
Zones curZone;
if(!zVec.empty())
{
curZone=zVec.back();
zVec.pop_back();
}
else return;
for(Colours c : colVec)
{
curZone.setZoneColour(c);
if(zSolVec.capacity()== 0)
{
std::vector<Zones> nzSolVec;
nzSolVec.push_back(curZone);
//zSolVec.push_back(curZone);
//recurse
mapColouring(colVec,nzSolVec,zVec);
}
else
{
//std::vector<Zones> :: iterator it;
//Zones lastZone = zSolVec.back();
bool sidematch = false;
for(int i : zSolVec.back().sides)
{
for(int j : curZone.sides)
{
if(i==j) sidematch = true;
}
}
if( (sidematch == true )&& (zSolVec.back().getZoneColour() != curZone.getZoneColour()) )
{
zSolVec.push_back(curZone);
//recurse
mapColouring(colVec,zSolVec,zVec);
}
else if(sidematch == false && (zSolVec.back().name != curZone.name) )
{
zSolVec.push_back(curZone);
//recurse
mapColouring(colVec,zSolVec,zVec);
}
else if((sidematch == true) && (zSolVec.back().getZoneColour() == curZone.getZoneColour()))
{
//branch end
return ;
}
}
}
}
}
Задача ещё не решена.
Других решений пока нет …