首页 > 代码库 > codevs 2292 图灵机游戏
codevs 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格，结束游戏
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<queue> 5 using namespace std; 6 const int maxn=666666; 7 int map[maxn]; 8 int dis[maxn]; 9 bool vis[maxn];10 queue<int>q;int n;11 void spfa(int s)12 {13 dis[s]=1;14 vis[s]=1;15 q.push(s);16 while(!q.empty())17 {18 int p=q.front();19 q.pop();20 if(!vis[map[p]])21 {22 q.push(map[p]);23 vis[map[p]]=1;24 dis[map[p]]=dis[p]+1;25 }26 if(!vis[p+1]&&p+1<=n)27 {28 q.push(p+1);29 vis[p+1]=true;30 dis[p+1]=dis[p]+1;31 }32 if(!vis[p-1]&&p-1>1)33 {34 q.push(p-1);35 vis[p-1]=1;36 dis[p-1]=dis[p]+1;37 }38 }39 return;40 }41 int main()42 {43 scanf("%d",&n);44 if(n==1){cout<<0;return 0;}45 for(int i=1;i<=n;i++)46 scanf("%d",&map[i]);47 spfa(map[1]);48 printf("%d\n",dis[n]);49 return 0;50 }
codevs 2292 图灵机游戏
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。