2292 图灵机游戏

 时间限制: 1
s

 空间限制: 64000
KB

 题目等级 : 黄金
Gold 

 

题目描述 Description

【Shadow 1】第二题

Shadow最近知道了图灵机是什么(Shadow:就是一行格子和一个机器头移来移去的呗!),于是他突发奇想,创造了一个新游戏——“图灵机游戏”(Shadow:好听吧?)。

游戏规则如下:

在一条长长的纸上有N个格子,每个格子上都有一个数,第i格的数记为Ai,机器头刚开始在第1格。这个游戏有两个操作:

1.如果现在在第i格,则可以移动机器头到第Ai格;

2.把某个Ai减少或增加1。

然而,fotile96看了之后却不以为然。“嗯,你挑战一下用最少次数使机器头到达第N格吧,这样好玩些……”

现在,Shadow已经快Crazy了。于是,Shadow把脸转向了你……

输入描述 Input Description

第1行,1个整数N;

第2行,N个整数Ai。

输出描述 Output Description

1行,1个整数,为最少的操作次数。

样例输入 Sample Input

5

3 4 2 5 3

样例输出 Sample Output

3

数据范围及提示 Data Size & Hint

对于30%的数据,1≤N≤10;
对于60%的数据,1≤N≤1000;
对于100%的数据,1≤N≤100000,1≤Ai≤N。

<h4>样例解释</h4>

1.先将第1格的值加1

2.跳到第4格

3.跳到第5格,结束游戏

思路:bfs;

 1 #include<cstdio>
 2 int num[100010];
 3 int team[100010],head,tail;
 4 int s[100010];
 5 int n;
 6 bool vis[100001];
 7 void bfs()
 8 {
 9     team[tail++]=num[1];
10     vis[num[1]]=1;
11     s[num[1]]=1;
12     while(head<=tail)
13     {
14         int d=team[head++];
15         if(d==n)return ;
16         if(!vis[num[d]])
17         {
18             team[tail++]=num[d];
19             s[num[d]]=s[d]+1;
20             vis[num[d]]=1;
21         }
22         if(d>0&&!vis[d-1])
23         {
24             team[tail++]=(d-1);
25             s[d-1]=s[d]+1;
26             vis[d-1]=1;
27         }
28         if(d<n&&!vis[d+1])
29         {
30             team[tail++]=(d+1);
31             s[d+1]=s[d]+1;
32             vis[d+1]=1;
33         }
34     }
35 }
36 int main()
37 { 
38     scanf("%d",&n);
39     for(int i=1;i<=n;++i)
40         scanf("%d",&num[i]);
41     bfs();
42     printf("%d",s[n]);
43     return 0;
44 }

 

2292 图灵机游戏,2292图灵机

2292 图灵机游戏

 

时间限制: 1 s
空间限制: 64000 KB 题目等级 : 黄金 Gold
        题目描述 Description

【Shadow 1】第二题

Shadow最近知道了图灵机是什么(Shadow:就是一行格子和一个机器头移来移去的呗!),于是他突发奇想,创造了一个新游戏——“图灵机游戏”(Shadow:好听吧?)。

游戏规则如下:

在一条长长的纸上有N个格子,每个格子上都有一个数,第i格的数记为Ai,机器头刚开始在第1格。这个游戏有两个操作:

1.如果现在在第i格,则可以移动机器头到第Ai格;

2.把某个Ai减少或增加1。

然而,fotile96看了之后却不以为然。“嗯,你挑战一下用最少次数使机器头到达第N格吧,这样好玩些……”

现在,Shadow已经快Crazy了。于是,Shadow把脸转向了你……

输入描述 Input Description 第1行,1个整数N; 第2行,N个整数Ai。 输出描述
Output Description

1行,1个整数,为最少的操作次数。

样例输入 Sample Input 5 3 4 2 5 3 样例输出 Sample Output

3

数据范围及提示 Data Size & Hint

对于30%的数据,1≤N≤10;
对于60%的数据,1≤N≤1000;
对于100%的数据,1≤N≤100000,1≤Ai≤N。

<h4>样例解释</h4> 1.先将第1格的值加1 2.跳到第4格
3.跳到第5格,结束游戏    

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<queue>
 5 #include<cstdlib>
 6 using namespace std;
 7 const int MAXN=10000001;
 8 int n;
 9 int a[MAXN];
10 int vis[MAXN];
11 int dis[MAXN];
12 void bfs()
13 {
14     int step=0;
15     queue<int>q;
16     q.push(a[1]);
17     vis[a[1]]=1;
18     dis[a[1]]=1;
19     while(q.size()!=0)
20     {
21         int p=q.front();
22         if(p==n)return ;
23         q.pop();
24                 if(vis[a[p]]==0)
25                 {
26                     q.push(a[p]);
27                     dis[a[p]]=dis[p]+1;
28                     vis[a[p]]=1;
29                 }
30                 if(vis[p+1]==0&&p<n)
31                 {
32                     q.push(p+1);
33                     dis[p+1]=dis[p]+1;
34                     vis[p+1]=1;
35                     //a[p]++;
36                 }
37                 if(vis[p-1]==0&&p>0)
38                 {
39                     q.push(p-1);
40                     dis[p-1]=dis[p]+1;
41                     vis[p-1]=1;    
42                 }    
43     }
44     
45 }
46 int main()
47 {
48     scanf("%d",&n);
49     for(int i=1;i<=n;i++)
50     {
51         scanf("%d",&a[i]);
52     }
53     bfs();
54     printf("%d",dis[n]);
55     return 0;
56 }

 

http://www.bkjia.com/cjjc/1208039.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1208039.htmlTechArticle2292 图灵机游戏,2292图灵机 2292 图灵机游戏
时间限制: 1 s 空间限制: 64000 KB 题目等级 : 黄金 Gold 题目描述
Description 【Shadow 1】第二题 Shado…

admin

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注