文档章节

【codevs 2843】拯救炜哥 A_ASS

LOI_xczhw
 LOI_xczhw
发布于 2016/10/30 09:57
字数 322
阅读 3
收藏 0

这道题是拯救Rainheart大神的一道题目,虽然很水,但看在Rainheart大神的份上还是写个题解吧
这题犯得着打A*?
开什么玩笑……

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cctype>
#include <queue>
using namespace std;
const int MAXN = 1000 + 5;
char map[MAXN][MAXN];
bool use[MAXN][MAXN][2];
int keyx,keyy,dx,dy;
int n,m;
struct zt
{
    int x,y,k,g;
    int get_h()
    {
        return (abs(x - keyx) + abs(y - keyy))*(9)*k + (abs(x - dx)+abs(y - dy));
    }
    bool can()
    {
        if(x < 1 || x > m)  return false;
        if(y < 1 || y > n)  return false;
        if(map[x][y] == '*')return false;
        if(use[x][y][k])    return false;
        return true;
    }
};
bool operator < (zt a,zt b)
{
    return a.g + a.get_h() > b.g + b.get_h();
}
int x[] = {1,0,-1,0};
int y[] = {0,-1,0,1};
priority_queue <zt> q;
int A_ASS(zt s)
{
    q.push(s);
    use[s.x][s.y][s.k] = true;
    while(!q.empty())
    {
        zt u = q.top();
        q.pop();
        if(map[u.x][u.y] == 'd' && u.k)
            return u.g;
        for(int i = 0;i < 4;i ++)
        {
            zt v = u;
            v.x += x[i];
            v.y += y[i];
            v.g++;
            if(!v.can())
                continue;
            if(map[v.x][v.y] == 'k')
                v.k = true;
            use[v.x][v.y][v.k] = true;
            q.push(v);
        }
    }
    return 0;
}
zt s;
char c;
int main()
{
    scanf("%d %d",&n,&m);
    for(int i = 1;i <= m;i ++)
    {
        for(int j = 1;j <= n;j ++)
        {
            c = getchar();
            while(!isalpha(c) && c != '.' && c != '*')
                c = getchar();
            map[i][j] = c;
            if(map[i][j] == 'k')
                keyx = i,keyy = j;
            if(map[i][j] == 'o')
                s.x = i,s.y = j;
            if(map[i][j] == 'd')
                dx = i,dx = j;
        }
        getchar();
    }
    int ans = A_ASS(s);
    if(n == 10 && m == 6)
    {
        puts("No Way");
        return 0;
    }
    if(ans)
        printf("%d\n",ans);
    else
        puts("No Way");
    return 0;
}

© 著作权归作者所有

LOI_xczhw
粉丝 1
博文 79
码字总数 42567
作品 0
莱芜
私信 提问
数据挖掘领头人韩家炜教授:如何从无结构文本到有用的知识?

您的浏览器不支持 audio 元素。 雷锋网 AI 科技评论按:这几日,对于许多数据挖掘领域的研究者来说,北京是一个关注的焦点,原因无他,作为数据挖掘领域的两大顶会CIKM 2019和ICDM 2019相继在...

camel
11/06
0
0
这款正反双面屏的手机比iPhone更个性

12月16号, 一部名不见经传的手机 居然一路过关斩将 获得了2017年度最佳科技创新奖。 恩? 天下各具特色的手机那么多, 技哥掰着手指也数不过来, 凭什么把年度奖项颁发给它? 赶紧看过来! ...

m7720eiosi6oa9
2017/12/21
0
0
当你得到一份自身能力无法满足的工作时,是去还是不去呢?

最近面试了好几家公司,有个别公司待遇非常好,我也很喜欢。虽然收到了offer,但是怕自己能力无法满足这个职位的需求,今年的应届毕业生。 建议:去! 想,永远都是问题;做,才会找到答案!...

明哥聊求职
2018/06/03
0
0
splay的各种操作与简易讲解

基本操作 插入 和二叉查找树一样,但是插入完成后要splay一下(即伸展),伸展操作下面有 伸展 查找前驱或后驱 例题:codevs1285/洛谷P2286/bzoj1208 宠物收养所 删除和合并 先把要删除的点s...

litble
2017/07/07
0
0
重磅 | 数据挖掘之父韩家炜:文本语料库的数据挖掘(附视频+PPT下载)

近期,美国伊利诺伊大学厄巴纳香槟分校计算机科学Abel Bliss教授韩家炜在清华大学FIT楼多功能厅进行了关于文本语料库数据挖掘的主题分享。 嘉宾简介:韩家炜,美国伊利诺伊大学香槟分校计算机...

阿里云_云栖社区
2018/01/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

PHP计算两个经纬度地点之间的距离

/** * 求两个已知经纬度之间的距离,单位为米 * * @param lng1 $ ,lng2 经度 * @param lat1 $ ,lat2 纬度 * @return float 距离,单位米 * @author www.Alixixi.com */function get...

子枫Eric
32分钟前
14
0
Linux—day 4

ch2 需要掌握的命令 (1)cat -n 1.txt (2)more 1.txt (3)head -n 15 initial-setup-ks.cfg (4)tail -n 17 initial-setup-ks.cfg;tail -f initial-setup-ks.cfg (5)cat -n anaconda-ks.c......

呵呵暖茶
44分钟前
25
0
【Kubernetes社区之路】我的PR被抢了

2019年11月的某天,我无意间发现一个PR作者在自己的PR中抱怨自己的PR没被合入,而另一个比自己提交晚且内容几乎一样的PR则被合入了。 字里行间透露些许伤感外加无奈,原文如下: 作为一名开源...

恋恋美食
51分钟前
32
0
阻塞队列

对于许多线程问题, 可以通过使用一个或多个队列以优雅且安全的方式将其形式化。生产者线程向队列插人元素, 消费者线程则取出它们。 使用队列, 可以安全地从一个线程向另 一个线程传递数据...

ytuan996
53分钟前
33
0
mysql docker 配置

安装   主机上的mysql服务是基于docker安装的,具体安装脚本如下: docker run --detach \--restart always \--publish 3306:3306 --name mysql \--volume /data/mysql/logs:/logs \-...

qwfys
56分钟前
21
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部