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

search--01

2022-08-10 12:06:00 【51CTO】

题目大概：

There are many lines connecting multiple routers,Signals cannot be the same between connected routers,Ask at least several signals.

思路：

This is actually a coloring problem in high school.

There are many connected graphs in one plane,Each two connected graphs have a different color,Ask the minimum number of colors that can be used to paint the picture.

Here is the four-color theorem,That's four colors at most.

那就好办了,Cycle from one color,Starts painting each time a certain number of colors are given,开始递归,Paint from the first,And automatically determine whether it is adjacent to it and he is the same color,是则结束,不是则继续,when the color runs out,Not finished painting yet.When all painted,结束.

感想：

Plus a deep search for the four-color theorem.

代码：

       
       #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.