计蒜客 密码锁(BFS)

摘要:
https://www.jisuanke.com/course/1797/121114Description现在一项紧急任务是打开密码锁。密码由四位数字组成,每一位数字从1到9。您可以一次从任何数字加1或减1。当9与1相加时,数字将变为1。当1与1相减时,数字会变为9。您还可以与邻居交换数字,并将每个动作记录为一个步骤。现在,您的任务是使用最小的步骤来打开锁。注意:最左边的数字不是最右边数字的邻居。我

https://www.jisuanke.com/course/1797/121114

Description

现在一个紧急的任务是打开一个密码锁。密码由四位数字组成,每个数字从 1 到 9 进行编号。每次可以对任何数字加 1 或减 1。当将9加 1 时,数字将变为1,当1减 1 的时,数字将变为9。您也可以与邻居交换数字,每一个行动记做一步。现在你的任务是使用最小的步骤来打开锁。
注意:最左边的数字不是最右边数字的邻居。

Input

第一行输入四位数字,表示密码锁的初始状态。

第二行输入四位数字,表示开锁的密码。

Output

输出一个整数,表示最小步骤。

样例输入

1234
2144

样例输出

2 

这道题最开始想不到用搜索来做。

不过这种题目还是很容易使用bfs来完成。

对于这道题目我们采用的标记方法和平时的标记也不太一样,我们是标记我们到达过的状态。

我们可以就是通过四维数组来完成标记,把由4个数字组成的一组密码记为一种状态,即:当密码为abcd时,对应的标记就应该记为vis[a][b][c][d]=1。

每次我们可以的操作有三种,第一种对于四位数字中的某一位加一,第二种对于四位数字中的某一位减一,第三种对于四位数字进行交换。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <string>
 5 #include <math.h>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <stack>
 9 #include <queue>
10 #include <set>
11 #include <map>
12 #include <sstream>
13 const int INF=0x3f3f3f3f;
14 typedef long long LL;
15 using namespace std;
16 
17 struct node
18 {
19     int num[4];
20     int step;
21 }first,last;
22 int vis[11][11][11][11];
23 
24 void BFS()
25 {
26     queue<node> qe;
27     node t;
28     t=first;
29     qe.push(t);
30     vis[t.num[0]][t.num[1]][t.num[2]][t.num[3]]=1;
31     while(!qe.empty())
32     {
33         t=qe.front();
34         qe.pop();
35         if(t.num[0]==last.num[0]&&t.num[1]==last.num[1]&&t.num[2]==last.num[2]&&t.num[3]==last.num[3])
36         {    //BFS出口 
37             printf("%d
",t.step);
38             return ;
39         }
40         for(int i=0;i<4;i++)//+1 
41         {
42             node next=t;
43             next.num[i]++;
44             if(next.num[i]==10) next.num[i]=1;
45             if(!vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]])
46             {
47                 vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]]=1;
48                 next.step++;
49                 qe.push(next);
50             }
51         }
52         for(int i=0;i<4;i++)//-1
53         {
54             node next=t;
55             next.num[i]--;
56             if(next.num[i]==0) next.num[i]=9;
57             if(!vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]])
58             {
59                 vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]]=1;
60                 next.step++;
61                 qe.push(next);
62             }
63         }
64         for(int i=0;i<3;i++)//交换 
65         {
66             node next=t;
67             swap(next.num[i],next.num[i+1]);
68             if(!vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]])
69             {
70                 vis[next.num[0]][next.num[1]][next.num[2]][next.num[3]]=1;
71                 next.step++;
72                 qe.push(next);
73             }
74         }    
75     }
76 }
77 
78 int main()
79 {
80     #ifdef DEBUG
81     freopen("sample.txt","r",stdin);
82     #endif
83     
84     char str1[5];
85     char str2[5];
86     scanf("%s %s",str1,str2);
87     for(int i=0;i<4;i++)
88     {
89         first.num[i]=str1[i]-'0';
90         last.num[i]=str2[i]-'0';
91     }
92     BFS();
93     
94     return 0;
95 }

-

免责声明:文章转载自《计蒜客 密码锁(BFS)》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇OC基础 文件管理融合趋势下基于 Flink Kylin Hudi 湖仓一体的大数据生态体系下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

随便看看

[转载]su认证失败

我认为桌面用户拥有更高的安全性是合适的;但是,可以将服务器设置为允许“su”作为root用户,但不允许root用户直接登录。问题如下:1me@ubuntu:~$su2Password:˂---在安装过程中输入root用户的密码。3su:身份验证失败允许su root。这很简单。您只需要重置密码。...

OpenWrt路由器通过LuCI界面实现Guest SSID功能

此外,OpenWrt路由器上的访客SSID不会受到主SSID的MAC地址过滤功能的影响,这是番茄路由器的优势。...

Jmeter中获取返回结果中的值

在jmeter的测试中,通常需要在下一个请求中使用上一个请求的返回值。如何获得返回值非常重要。插件下载地址为:http://jmeter-plugins.org/wiki/JSONPathExtractor/下载后,将lib文件夹放在jmeter目录中。...

JRebel 6 破解版及使用方法

2.解压下载的jrebel6.0.0-crack.zip、jrebel6.0 jar包和破解文件。假设文件在D:/jrebel步骤:1中解压缩。eclipse下载jrebe插件,可以在市场上下载。2.打开eclipse的窗口首选项jrebel,打开优势选项卡,并将jar包的路径指向D:/jrebel/jrebel.jar。用CMD打开DOS窗口,输入cd/d...

GPU与CPU

GPU和CPU CPU,也称为中央处理单元,主要由控制器、运算单元、寄存器、高速缓冲区和数据/控制/状态总线组成。GPU GPU称为GraphicsProcessingUnit,即图形处理器。GPU最初是为终端游戏设计的。由于对游戏中的大量数据重复相同的操作,GPU面临着类型高度统一、相互依赖的大规模数据。GPU的内核远多于CPU。它向多个内核发送相同的指令...

HTML5表单之input 类型- Date Pickers(日期选择器)

HTML5有几种新的输入类型用于选择日期和时间:日期:选择日期、月份、年份月份:选择月份、年份星期:选择星期和年份时间:选择时间datetime local:选择时间、日期、月份和年份datetime:选择时间、,年示例1:日期示例2:月示例3:周示例4:时间˂inputtype=“time”name=“tart_time”value=“”//示例5:dat...