1.【题目描述】
给定无向图，要你判断有多少种着 {MOD}方案。（相邻的节点不能着同一种颜 {MOD}） 【输入】
第一个整数n代表无向图的节点个数
第二个整数k表示无向图的边数
第三个整数m表示可以涂的颜 {MOD}种数
下面k行代表无向图的边
【输入样例】
5 8 4
1 2
1 3
1 4
2 3
2 4
2 5
3 4
4 5
【输出】
48 代表48种涂 {MOD}方案 【思路】
直接采用dfs深搜
本题无向图的邻接矩阵为：
0 1 1 1 0
1 0 1 1 1
1 1 0 1 0
1 1 1 0 1
0 1 0 1 0
搜索限制条件就是，如果某个节点j与节点k相邻，那么查找节点j的颜 {MOD}是否和节点k要涂的颜 {MOD}一样，如果一样就不能涂。与全排列的dfs就是剪枝语句的区别。 参考代码： /* dfs，先用邻接矩阵存无向图 5 8 4 1 2 1 3 1 4 2 3 2 4 2 5 3 4 4 5 48 邻接矩阵: 0 1 1 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 0 1 0 1 0 1 0 ---------- 4 4 3 1 2 1 3 1 4 3 4 12 ----------- */ #include using namespace std; const int maxn = 100; int a[maxn][maxn]; int n, k, m; int c[maxn]; //c[i]表示节点i的颜 {MOD}值 int ans = 0; bool panduan(int k, int color) { for(int j = 1;j <= n;j++) { if(a[k][j] == 1) //如果j节点跟我相邻 { if(color == c[j]) //如果j节点的颜 {MOD}与我将要涂的颜 {MOD}相同，那么不行！ return false; } } return true; } void dfs(int k) //k代表节点的序号 { if(k == n + 1) //如果搜到了最后一个节点 { ans++; return ; } //枚举该节点可以涂的颜 {MOD} for(int i = 1;i <= m;i++) { if(panduan(k, i)) //判断该颜 {MOD}是否可以涂 { c[k] = i; //涂上 dfs(k + 1); c[k] = 0; } } } int main() { cin >> n >> k >> m; for(int i = 1;i <= k;i++) { int x, y; cin >> x >> y; a[x][y] = 1; a[y][x] = 1; } dfs(1); if(ans == 0) cout << "-1" << endl; else cout << ans << endl; return 0; }

---

2
【题目描述】
求解涂棋盘问题。小易有一块n * n的棋盘，棋盘的每一个格子都为黑 {MOD}或者白 {MOD}，小易现在要用红 {MOD}去涂画棋盘。小易会找出棋盘的某一列中拥有相同颜 {MOD}的最大区域去涂画，请算一下他会涂多少棋格 输入：
3
BWW
BBB
BWB 【输出】
3 这题更简单了，直接暴力循环搜就可以出结果了。这题也是被分到课本的蛮力法下面。 /* 3 BWW BBB BWB 3(第一列的3个B涂成红 {MOD}) */ #include using namespace std; const int maxn = 100; int n; char m[maxn][maxn]; int main() { cin >> n; for(int i = 1;i <= n;i++) { for(int j = 1;j <= n;j++) { cin >> m[i][j]; } } int b = 0, w = 0, t = 0, max_res = 0; //存储黑 {MOD}的数目和白 {MOD}的数目 for(int j = 1;j <= n;j++) { //这些要重新置0，max_res要做参照，所以max_res不用清0 t = 0; b = 0; w = 0; for(int i = 1;i <= n;i++) { if(m[i][j] == 'B') b++; else if(m[i][j] == 'W') w++; } t = max(b, w); //找出相同颜 {MOD}最多的砖块 if(t > max_res) max_res = t; //那么存到最大值中去 } cout << max_res << endl; return 0; } 简单回顾一下蛮力的题型