P1135 奇怪的电梯【一题多解】

Mathison · 2018-10-01 20:53:25 · 题解

这题是黄题……不是特别难……所以我用四种方法写了这个题

一、dfs

思路很简单，从起点开始，只要没越界就向上下搜，全部搜完得到答案

#include<cstdio>
#include<iostream>
using namespace std;
int n,a,b,ans=0x7ffffff;
int to[205];
bool vis[205];
void dfs(int now,int sum)//now表示当前搜到的楼层,sum表示按钮次数
{
    if(now==b) ans=min(ans,sum);
    if(sum>ans) return;
    vis[now]=1;
    //不越界就搜
    if(now+to[now]<=n&&!vis[now+to[now]]) dfs(now+to[now],sum+1);
    if(now-to[now]>=1&&!vis[now-to[now]]) dfs(now-to[now],sum+1);
    vis[now]=0;//回溯
}
int main()
{
    scanf("%d%d%d",&n,&a,&b);
    for(int i=1;i<=n;i++) scanf("%d",&to[i]);
    vis[a]=1;
    dfs(a,0);
    if(ans!=0x7ffffff) printf("%d",ans);
    else printf("-1");
    return 0;
}

54ms

二、bfs

和dfs思路一样，只是以广度优先

#include<bits/stdc++.h>
using namespace std;
int n,a,b,to[205];
bool vis[205];
struct node{int id,step;}x;//id表示楼层号，step表示按钮次数
queue<node> q;
int main()
{
    scanf("%d%d%d",&n,&a,&b);
    for(int i=1;i<=n;i++) scanf("%d",&to[i]);
    q.push((node){a,0});
    while(q.size())
    {
        x=q.front();q.pop();
        if(x.id==b) break;
        if(x.id+to[x.id]<=n&&!vis[x.id+to[x.id]])
        {
            q.push((node){x.id+to[x.id],x.step+1});
            vis[x.id+to[x.id]]=1;
        }
        if(x.id-to[x.id]>=1&&!vis[x.id-to[x.id]])
        {
            q.push((node){x.id-to[x.id],x.step+1});
            vis[x.id-to[x.id]]=1;
        }
    }
    if(x.id==b) printf("%d",x.step);
    else printf("-1");
    return 0;
}

28ms

明显比深搜快了

三、floyd

我们发现电梯上下楼的路径可以看做有向边，所以可以用图论做法

~~主要是floyd好写额~~

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dis[201][201],n,a,b,x;
int main()
{
    scanf("%d%d%d",&n,&a,&b);
    for(int i=1;i<=n;i++)
        for(int j=1;j<i;j++)
            dis[i][j]=dis[j][i]=1e8;
    for(register int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        if(i+x<=n) dis[i][i+x]=1;
        if(i-x>=1) dis[i][i-x]=1;
    }
    for(int k=1;k<=n;++k)
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
                if(dis[i][j]>dis[i][k]+dis[k][j])
                    dis[i][j]=dis[i][k]+dis[k][j];
    if(dis[a][b]<1e8) printf("%d",dis[a][b]);
    else printf("-1");
    return 0;
}

153ms

不是很理想

四、spfa

只有考虑起点到终点用floyd其实有点费……

单源最短路spfa足以（不放心的话写堆优化dijskra）

#include<bits/stdc++.h>
using namespace std;
const int N=210;
int n,a,b,tot,ver[2*N],head[N],next[2*N],dis[N];
bool vis[N];
queue<int> q;
void add(int x,int y)
{
    ver[++tot]=y;
    next[tot]=head[x];
    head[x]=tot;
}
void spfa()
{
    dis[a]=0;
    vis[a]=1;
    q.push(a);
    while(q.size())
    {
        int x=q.front();q.pop();vis[x]=0;
        for(int i=head[x];i;i=next[i])
        {
            int y=ver[i];
            if(dis[y]>dis[x]+1)
            {
                dis[y]=dis[x]+1;
                if(!vis[y])
                {
                    q.push(y);
                    vis[y]=1;
                }
            }
        }
    }
}
int main()
{
    scanf("%d%d%d",&n,&a,&b);
    for(int i=1;i<=n;i++)
    {
        int x; 
        scanf("%d",&x);
        if(i+x<=n) add(i,i+x);
        if(i-x>=1) add(i,i-x);
    }
    memset(dis,0x3f3f3f3f,sizeof dis);
    spfa();
    if(dis[b]<0x3f3f3f3f) printf("%d",dis[b]);
    else printf("-1");
    return 0;
}

27ms

也表明了本质上spfa和bfs其实相同原理的~~（spfa比较玄学）~~

END