当前位置：网站首页>搜索--01

搜索--01

2022-08-10 11:13:00 【51CTO】

题目大概：

多个路由器之间有很多线相连，相联的路由器之间信号不能一样，问最少有几种信号。

思路：

这其实是高中的染色问题。

在一个平面上有很多相接的图，每两个相接的图有不同的颜色，问最少可以用多少种颜色把图涂好。

这里有四色定理，就是最多是四种颜色。

那就好办了，从一种颜色开始循环，每次给定一定数量的颜色开始涂色，开始递归，从第一个开始涂，并自动判定与它相邻的是否和他同一颜色，是则结束，不是则继续，当颜色用完，还没涂完结束。当全部涂完，结束。

感想：

加上四色定理的深度搜索。

代码：

       
       #include <iostream>
       
       #include <string>
       
       #include <cstring>
       
       using 
       
       namespace 
       
       std;
       
       int 
       
       a[
       
       28][
       
       28];
       
       int 
       
       s[
       
       28];
       
       int 
       
       q,
       
       t,
       
       n;
       
       int 
       
       dfs(
       
       int 
       
       k)
       
{
       
       if(
       
       k
       
       ==
       
       n
       
       +
       
       1){
       
       t
       
       =
       
       1;
       
       return 
       
       0;}
       
       for(
       
       int 
       
       j
       
       =
       
       1;
       
       j
       
       <=
       
       q;
       
       j
       
       ++)
       
 {
       
       s[
       
       k]
       
       =
       
       j;
       
       int 
       
       o
       
       =
       
       1;
       
       for(
       
       int 
       
       i
       
       =
       
       1;
       
       i
       
       <
       
       k;
       
       i
       
       ++)
       
 {
       
       if(
       
       a[
       
       k][
       
       i]
       
       &&
       
       s[
       
       k]
       
       ==
       
       s[
       
       i])
       
       o
       
       =
       
       0;
       
 }
       
       if(
       
       o)
       
       dfs(
       
       k
       
       +
       
       1);
       
 }
       
       return 
       
       0;
       
}
       
       int 
       
       main()
       
{
       
       string 
       
       m;
       
       while(
       
       cin
       
       >>
       
       n)
       
{
       
       if(
       
       n
       
       ==
       
       0)
       
       break;
       
       memset(
       
       a,
       
       0,
       
       sizeof(
       
       a));
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       n;
       
       i
       
       ++)
       
{
       
       cin
       
       >>
       
       m;
       
       for(
       
       int 
       
       j
       
       =
       
       2;
       
       j
       
       <
       
       m.
       
       size();
       
       j
       
       ++)
       
{
       
       a[
       
       m[
       
       0]
       
       -
       
       'A'
       
       +
       
       1][
       
       m[
       
       j]
       
       -
       
       'A'
       
       +
       
       1]
       
       ==
       
       1;
       
       a[
       
       m[
       
       j]
       
       -
       
       'A'
       
       +
       
       1][
       
       m[
       
       0]
       
       -
       
       'A'
       
       +
       
       1]
       
       =
       
       1;
       
}
       
}
       
       t
       
       =
       
       0;
       
       for(
       
       q
       
       =
       
       1;
       
       q
       
       <=
       
       3;
       
       q
       
       ++)
       
{
       
       memset(
       
       s,
       
       0,
       
       sizeof(
       
       s));
       
       dfs(
       
       1);
       
       if(
       
       t)
       
       break;
       
}
       
       if(
       
       q
       
       ==
       
       1)
       
       cout
       
       <<
       
       q
       
       <<
       
       " channel needed."
       
       <<
       
       endl;
       
       else 
       
       cout
       
       <<
       
       q
       
       <<
       
       " channels needed."
       
       <<
       
       endl;
       
}
       
       return 
       
       0;
       
}
      
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.