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格，结束游戏

ac：

1 #include<iostream>
 2 
 3 #include<cstdio>
 4 
 5 using namespace std;
 6 
 7 int a[100001],n,v[100001]= {0},ans[100001],q[100001];
 8 
 9 void bfs()
10 
11 {
12 
13     q[1]=a[1];
14 
15     v[a[1]]=1;
16 
17     ans[a[1]]=1;
18 
19     int head=1,tail=1;
20 
21     while(head<=tail)
22 
23     {
24 
25         int u=q[head];
26 
27         if(u==n) return;
28 
29         if(!v[a[u]])
30 
31         {
32 
33             q[++tail]=a[u];
34 
35             ans[a[u]]=ans[u]+1;
36 
37             v[a[u]]=1;
38 
39         }
40 
41         if(u<n&&!v[u+1])
42 
43         {
44 
45             q[++tail]=u+1;
46 
47             ans[u+1]=ans[u]+1;
48 
49             v[u+1]=1;
50 
51         }
52 
53         if(u>0&&!v[u-1])
54 
55         {
56 
57             q[++tail]=u-1;
58 
59             ans[u-1]=ans[u]+1;
60 
61             v[u-1]=1;
62 
63         }
64 
65         ++head;
66 
67     }
68 
69 
70 
71 }
72 
73 int main()
74 
75 {
76 
77     cin>>n;
78 
79     if(n==1) 
80     {
81         cout<<"0"<<endl;
82         return 0;
83     }
84 
85     for(int i=1; i<=n; i++)
86 
87         cin>>a[i];
88 
89     bfs();
90 
91     cout<<ans[n];
92 
93     return 0;
94 
95 }

View Code

no ac

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(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 }

View Code