时间限制: 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 }