您现在的位置是:首页 > 学习之路 > ACM||算法ACM||算法

POJ-2251 Dungeon Master

卞振伟2019-07-25【ACM||算法】人已围观

简介POJ-2251 Dungeon Master
BFS
普通多维迷宫,最短时间.

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cstdio>

using namespace std;

const int maxn = 1e5+10;
int n, k;
int d[maxn];
int vst[maxn];

int bfs(){
    if(n == k)  //不能省略?
        return 0;
    queue<int> q;
    vst[n] = 1;
    q.push(n);
    while(!q.empty()){
        int p = q.front();
        q.pop();
        if(p == k){
            return d[p];
        }
        if(p+1 <= maxn && !vst[p+1]){
            q.push(p+1);
            vst[p+1] = 1;
            d[p+1] = d[p]+1;
        }
        if(p-1 >= 0 && !vst[p-1]){
            q.push(p-1);
            vst[p-1] = 1;
            d[p-1] = d[p]+1;
        }
        if(p*2 <= maxn && !vst[p*2]){
            q.push(p*2);
            vst[p*2] = 1;
            d[p*2] = d[p]+1;
        }
    }
}

int main(){
    scanf("%d%d", &n, &k);
    int ans = bfs();
    printf("%d", ans);
    return 0;
}

Tags:ACM   编程   个人   题解   算法   C|C++

很赞哦! ()

文章评论

站点信息

  • 建站时间:2018-11-25
  • 网站程序:帝国CMS7.5
  • 文章统计:118篇文章
  • 标签管理标签云
  • 统计数据百度统计
  • 网站地图XML网站地图
  • 微信公众号:扫描二维码,关注我的公众号
  • GitHub:扫描二维码,关注我的GitHub

客服在线

QQ客服

客服微信扫码

服务时间

周一至周日 9:00-21:00