//算法设计与分析 --- 回溯法
/*
回溯法---优化过的蛮力法,具有限界函数的深度优先生成法
使用剪枝函数,删除不可能出现的情况
根据相应约束条件找到问题的可行解||最优解
*/
/*
回溯法模板
注意分成横纵两个方面思考回溯
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { //注意i=0,i=start的区别
处理节点;
backtracking(路径，选择列表); // 递归 注意(i)和(i++)的区别
回溯，撤销处理结果
}
}
*/
#include<iostream>
#include<algorithm>
#include <vector>
/*
WA NT
WA SA
NT Q
NT SA
Q SA
Q NSW
NSW SA
NSW V
V SA
*/
using namespace std;
class graph{
private:
int **arr; //邻接矩阵存储图表信息
int l; //大小
int kind; //涂料的种类/数量
string *s; //存储各个区域的名称
int n; //存储边的的数量
int sum; //记录走过区域的总次数
vector<vector<int>> solutions; //存储具体的方案
public:
graph(){
kind=5; //决定颜色种类的数量为5
l=7;
s=new string[l]{"WA","NT","Q","SA","NSW","V","T"};
sum=0;
arr=new int*[l];
for(int i=0;i<l;i++)
arr[i]=new int[l];
for(int i=0;i<l;i++)
for(int j=0;j<l;j++)
arr[i][j]=0;
n=9;
while(n--){
string s1,s2;
cin>>s1>>s2;
arr[find(s1)][find(s2)]=arr[find(s2)][find(s1)]=1;
}
}
int find(const string& str){
for(int i=0;i<l;i++)
if(str==s[i])
return i;
return -1;
}
//普通回溯法解决涂色方案
void start(){
solveGraphColoring();
if (solutions.empty())
cout << "No solutions" << endl;
else
cout << "Total has " << solutions.size() << " methods" << endl;
cout << sum << endl;
}
bool isValid(vector<int> &colors, int node, int color) {
for (int i = 0; i < l; i++) {
if (arr[node][i] == 1 && colors[i] == color) {
return false;
}
}
return true;
}
void backtrack( vector<int> &colors, int node, vector<vector<int>> &so) {
if (node >= l) {
so.push_back(colors); // 找到一个可行解，将其存入解集
return;
}
for (int color = 1; color <= kind; color++) { // 尝试颜色
if (isValid( colors, node, color)) {
colors[node] = color; // 着色
backtrack(colors, node + 1, so); // 递归探索下一个节点
colors[node] = 0; // 撤销着色
sum++;
}
}
}
void solveGraphColoring() {
vector<int> colors(l, 0); // 存储节点的颜色，初始都为0
backtrack( colors, 0, solutions);
}
/*
效率提升方案
MRV 优先选择具有可填图颜色较少的变量
DH 选择当前约束最多的变量
*/
};
/*
int main() {
graph a;
a.start();
return 0;
}
*/
