首页 > 代码库 > 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。
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 }
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 }
2292 图灵机游戏
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。