今天，伟帅讲了两个追溯法的典型例题。 还很容易理解，记录下来吧~
回溯(有点崇拜的方法之一是，使用起来会很轻松。 如果没想到的话……)
n皇后问题
主题：用回溯法求解n后问题
输入：皇后数
输出：各方案
案例：
构想：从第一行开始确定皇后的位置。 如果皇后的配置没有结束的话，合适的位置没有了的话，请回去。 交流电源线：
# include bits/stdc.h # definelllonglongusingnamespacestd； int n； int m[101]、l[101]、r[101]； //m序列记录每列有无皇后，l序列记录左斜线有无皇后，r序列记录右斜线有无皇后int a[101][101]； int ans，记录每个方案的皇后位置； voidprin(inta[][101] ) for ) intI=0； in； I ) for(intj=0； jn-1； j ) printf('%d '，a[i][j]； printf(%d(n )，a[i][n-1]； (printf(--------(n ) )； }intchecked(intI ) ) for ) intj=0； jn； j () if (！ m[j]！ l[i j]！ r[I-jn]}{a[I][j]=I1； m[j]=l[i j]=r[i-j n]=1； //左斜线和右斜线的行和列的关系在此不再赘述。 如果感兴趣的话，去度娘if(I==n-1 )//叶节点就可以输出(prin(a )； ans； (else ) checked ) I1； 记得返回a[i][j]=0； m[j]=l[i j]=r[i-j n]=0； } } return ans； (}int main ) ) while(cinn ) ) { ans=0； memset(m，0，sizeof(m ) m )； memset(L，0，sizeof(l ) l )； memset(r，0，sizeof(r ) r )； memset(a，0，sizeof(a ) a )； 已检查(0； printf ('总方案数为%dn )、ans )； } return 0； )2.图的m着色问题
主题：给出有向连通图g和m种不同的颜色。 用这些颜色对图g的各顶点进行着色，并在各顶点上涂上一种颜色。 有给g每条边的两个顶点涂上不同颜色的着色方法吗？ 请输出阴影方法。
思路：与全序列相同，1…按顺序做第n个颜色，但有回溯法的灵魂剪枝函数，去掉了很多不满足条件的路
交流电源线：
# include bits/stdc.h # definelllonglongusingnamespacestd； int n，m，k； int lu[1001][1001]； //节点之间是否有路，如果有则为1，如果没有则为0int c[1001]； //记录颜色intcheck(intt，int i ) ) for ) intj=1； jt； j () if ) Lu[t][j]==1c[j]==I ) return 0； } return 1； }voidsolve(intt ) if ) TN ) { int i； for(I=1； in； I ) printf('%d '，c[i]； printf(%d(n )，c[n]； (else ) for ) intj=1； j=k； j () if ) check(t，j ) ) { c[t]=j； Solve(t1； } } }}int main () while(cinnmk ) (memset ) Lu，0，sizeof ) Lu )； memset(c，0，sizeof(c ) c )； int i； int x，y； for(I=1； i=m； I ) { cinxy； lu[x][y]=1； lu[y][x]=1； (for ) I=1； i=k； I ) c(I )=I； solve(1； } return 0； )漫长的人生之路……