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

搜索--09

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

题目大概：

输入n组数据，每组数据两个四位素数。让第一个四位数变到第二个四位数，每步只能改一个数，改后的数也必须是素数，问最少经过几步改变可以成功。

思路:

用广度优先搜索。

先把所有的素数筛出来，方便判断，然后四位数一位一位的改变，把符合条件的数放到队列中，直到变为第二个数，输出改变次数。

感想：

数据过多，就把一类数据做成一个结构体，这样方便进队列，而且如果分多个队列，内存会不够。

代码：

       
       #include <iostream>
       
       #include <cstdio>
       
       #include <cstring>
       
       #include <queue>
       
       using 
       
       namespace 
       
       std;
       
       int 
       
       sushu[
       
       10001];
       
       int 
       
       biao[
       
       10001];
       
       struct 
       
       q
       
{
       
       int 
       
       bit[
       
       4];
       
       int 
       
       num;
       
       int 
       
       s;
       
};
       
       queue
       
       <
       
       q
       
       >
       
       a;
       
       void 
       
       w()
       
{
       
       int 
       
       i,
       
       j;
       
       for(
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       10001;
       
       i
       
       ++)
       
       sushu[
       
       i]
       
       =
       
       1;
       
       sushu[
       
       0]
       
       =
       
       0;
       
       sushu[
       
       1]
       
       =
       
       0;
       
       for(
       
       i
       
       =
       
       2;
       
       i
       
       <
       
       10001;
       
       i
       
       ++)
       
    {
       
       if(
       
       sushu[
       
       i]
       
       ==
       
       1)
       
        {
       
       for(
       
       j
       
       =
       
       i
       
       +
       
       i;
       
       j
       
       <
       
       10001;
       
       j
       
       +=
       
       i)
       
            {
       
       sushu[
       
       j]
       
       =
       
       0;
       
            }
       
        }
       
    }
       
}
       
       int 
       
       num(
       
       int 
       
       a[],
       
       int 
       
       b,
       
       int 
       
       c)
       
{
       
       int 
       
       s
       
       =
       
       0;
       
       for(
       
       int 
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       4;
       
       i
       
       ++)
       
    {
       
       if(
       
       i
       
       ==
       
       b)
       
       s
       
       =
       
       s
       
       *
       
       10
       
       +
       
       c;
       
       else
       
       s
       
       =
       
       s
       
       *
       
       10
       
       +
       
       a[
       
       i];
       
    }
       
       return 
       
       s;
       
}
       
       void 
       
       bfs(
       
       int 
       
       first,
       
       int 
       
       second)
       
{
       
       int 
       
       i,
       
       j,
       
       k;
       
       memset(
       
       biao,
       
       0,
       
       sizeof(
       
       biao));
       
       q 
       
       f,
       
       r;
       
       f.
       
       num
       
       =
       
       first;
       
       f.
       
       bit[
       
       3]
       
       =
       
       first
       
       %
       
       10;
       
       f.
       
       bit[
       
       2]
       
       =(
       
       first
       
       /
       
       10)
       
       %
       
       10;
       
       f.
       
       bit[
       
       1]
       
       =(
       
       first
       
       /
       
       100)
       
       %
       
       10;
       
       f.
       
       bit[
       
       0]
       
       =(
       
       first
       
       /
       
       1000)
       
       %
       
       10;
       
       f.
       
       s
       
       =
       
       0;
       
       a.
       
       push(
       
       f);
       
       while(
       
       !
       
       a.
       
       empty())
       
    {
       
       r
       
       =
       
       a.
       
       front();
       
       a.
       
       pop();
       
       if(
       
       r.
       
       num
       
       ==
       
       second)
       
        {
       
       cout
       
       <<
       
       r.
       
       s
       
       <<
       
       endl;
       
       break;
       
        }
       
       for(
       
       i
       
       =
       
       0;
       
       i
       
       <
       
       4;
       
       i
       
       ++)
       
{
       
       for(
       
       j
       
       =
       
       0;
       
       j
       
       <=
       
       9;
       
       j
       
       ++)
       
{
       
       if(
       
       j
       
       ==
       
       0
       
       &&
       
       i
       
       ==
       
       0)
       
       continue;
       
       if(
       
       r.
       
       bit[
       
       i]
       
       ==
       
       j)
       
       continue;
       
       else
       
{
       
       int 
       
       i1
       
       =
       
       num(
       
       r.
       
       bit,
       
       i,
       
       j);
       
       if(
       
       sushu[
       
       i1]
       
       &&!
       
       biao[
       
       i1]){
       
       biao[
       
       i1]
       
       =
       
       1;
       
       for(
       
       k
       
       =
       
       0;
       
       k
       
       <
       
       4;
       
       k
       
       ++)
       
{
       
       f.
       
       bit[
       
       k]
       
       =
       
       r.
       
       bit[
       
       k];
       
        }
       
       f.
       
       bit[
       
       i]
       
       =
       
       j;
       
       f.
       
       num
       
       =
       
       i1;
       
       f.
       
       s
       
       =
       
       r.
       
       s
       
       +
       
       1;
       
       a.
       
       push(
       
       f);
       
}
       
}
       
}
       
}
       
}
       
}
       
       int 
       
       main()
       
{
       
       int 
       
       n;
       
       int 
       
       first,
       
       second;
       
       w();
       
       cin
       
       >>
       
       n;
       
       while(
       
       n
       
       --)
       
    {
       
       cin
       
       >>
       
       first
       
       >>
       
       second;
       
       bfs(
       
       first,
       
       second);
       
       while(
       
       !
       
       a.
       
       empty()){
       
       a.
       
       pop();}
       
    }
       
       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.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.

原网站

版权声明
本文为[51CTO]所创，转载请带上原文链接，感谢
https://blog.51cto.com/u_15747246/5562797

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

搜索--09

边栏推荐

猜你喜欢

随机推荐