【模拟】--新飞行棋

Mercia ·

更新时间:2024-11-14

· 653 次阅读

UPC–2020.3.26

这题正解应该是dfs或bfs吧，只怪小生学艺不精，目前还未掌握到搜索的精髓，只能模拟一波了，模拟的不好，还请多多指教~~

时间限制: 1 Sec 内存限制: 128 MB

题目描述

期末考试终于结束了。Andy同学感觉松了一口气，他决定重温小时候的快乐时光–下飞行棋。
但是他弄丢了传统飞行棋需要的骰子，因此他发明了一种新型的飞行棋游戏，规则如下：棋盘上有n个格子，由近到远分别编号为1到n。对于1<=in,那么他就只能选择后退；同理如果a-Na<1，那么他就只能选择前进。保证不会出现既不能前进又不能后退的格子。
Andy学完编程后对一个问题很感兴趣：从编号s出发，至少需要经过几把，可以到达t点？（例如在a点选择往前走Na步，称之为一把）。

输入

第一行三个整数，分别为n，s，t意义如题面所述。
第二行n个正整数，第i个数为Ni。

输出

一个数，为最少经过的把数。如果s无法到达t，输出-1。

样例输入

6 6 4
1 2 2 3 1 2

样例输出

提示

对于前10%的数据，s=t；
对于前40%的数据，n<=200;
对于另外10%的数据，s无法到达t；
对于100%的数据，n<=200000;

用了一个很暴力的做法，能上或者能下就走一遍，如果进入死循环就输出-1！
直接来代码吧，注释跟上。

#pragma GCC optimize(2)
#pragma G++ optimize(2)
#include 
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 7;
const int mod = 1e9 + 7;
const int INF = 0x7fffffff;
ll n, m, b, x,h,temp=0, y,l=1,st1[maxn],st2[maxn],ans = 0, k;
//st1[i]表示到第i个一共前进和后退了多少次？
//st2[i]表示第i层的按键显示是多少？
ll st,en;
bool flag=true;
//pd=true 表示能走
//否则不能走(在下面有着非常关键的作用）
int main(){
    scanf("%lld%lld%lld",&n,&st,&en); //st表示最开始所在的位置，en表示目标的位置
    for(ll i=1;i<=n;i++)
    {
        st1[i]=-1;//首先将st数组初始化为-1，表示该位置没走过
        scanf("%lld",&st2[i]);
    }
    st1[st]=0;//开始步数为0
    while(st1[en]==-1&&flag)//该位置没走过并且下一步可以走
    {
        flag=false;//一开始假设下一步不能走
        for(ll i=1;i<=n;i++)
        {
            if(st1[i]==temp)
            {
                k=i+st2[i];//模拟前进
                if(k=1&&st1[k]==-1)//表示可以后退并且第k个位置没走过
                {
                    flag=true;
                    st1[k]=temp+1;//更新
                }
            }
        }
        temp++;
    }
    printf("%lld",st1[en]);//如果没走到这里输出-1，走到这里就输出对应的步数
    return 0;
}

当你感觉越来越吃力的时候，那是你在爬上升的陡坡。

作者：渣渣松

飞行棋

1024 个赞