AT46 リモコン

2019-10-03 23:24:17


题目描述:

搜索的裸题,只不过操作有点多,略烦。

思路:

看到其他大佬都在用dfs,迭代加深,打表,贪心等神奇算法,蒟蒻只得给出一个标准模板(怎么还有用结构体的……完全不用啊)

使用bfs求最短路径,因为数据小可以通过,只不过在push的时候要写6个if,烦。

最后注意下输出要换行。

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
queue<ll> q;
bool vis[41];
ll a,b,dis[41];
int main(){
    scanf("%lld%lld",&a,&b);
    q.push(a);
    vis[a]=1;
    dis[a]=0;
    while(!q.empty()){
        int now=q.front();
        if(now==b) {
            printf("%lld\n",dis[now]);
            return 0;
        }
        if(!vis[now-1]&&now-1>=0) vis[now-1]=1,q.push(now-1),dis[now-1]=dis[now]+1;
        if(!vis[now+1]&&now+1<=40) vis[now+1]=1,q.push(now+1),dis[now+1]=dis[now]+1;
        if(!vis[now-5]&&now-5>=0) vis[now-5]=1,q.push(now-5),dis[now-5]=dis[now]+1;
        if(!vis[now+5]&&now+5<=40) vis[now+5]=1,q.push(now+5),dis[now+5]=dis[now]+1;
        if(!vis[now-10]&&now-10>=0) vis[now-10]=1,q.push(now-10),dis[now-10]=dis[now]+1;
        if(!vis[now+10]&&now+10<=40) vis[now+10]=1,q.push(now+10),dis[now+10]=dis[now]+1;
        q.pop();
    }
    return 0;
}