文档章节

Honey Heist(mcpc2017 )

o
 osc_x4h57ch8
发布于 2018/04/24 00:17
字数 1246
阅读 0
收藏 0

精选30+云产品,助力企业轻松上云!>>>

5092: Honey Heist

时间限制: 1 Sec  内存限制: 128 MB
提交: 27  解决: 10
[提交][状态][讨论版][命题人:admin]

题目描述

0x67 is a scout ant searching for food and discovers a beehive nearby. As it approaches the honeycomb,0x67 can sense an area inside packed with dried honey that can be easily carried back to the nest and stored for winter. However, it must burrow through the honeycomb to reach the cell containing the sweet loot. If 0x67 can create a passage to the honey to help the other ants find it, it will do so before returning to the nest. The cells of the honeycomb are numbered in row major order, so cell IDs can be assigned as shown below:
When 0x67 discovers the opening to the honeycomb, it enters the cell. Some ants are stronger than others, depending on their age, so 0x67 can only chew through at most N cells before its jaw wears out and must return to the nest to recuperate. The honeycomb is hexagonal, and each edge length is R cells. 0x67 enters through a hole at location A and must get to the honey at location B by chewing a path through no more than N adjacent cells. Because ants can be competitive, 0x67 wants to reach the honey by chewing through the fewest possible cells. 0x67 can also sense some of the cells are hardened with wax and impossible to penetrate, so it will have to chew around those to reach the cell at location B.

Scout ants have rudimentary computational skills, and before 0x67 begins to chew, it will work out where it needs to go, and compute K, the least number of cells it needs to chew through to get from A to B, where B is the Kth cell. If K > N, 0x67 will not be strong enough to make the tunnel. When 0x67 returns to the nest, it will communicate to its nestmates how many cells it chewed through to get to B, or will report that it could not get to the honey.

输入

The input contains two lines. The first line contains five blank separated integers: R N A B X
R: the length (number of cells) of each edge of the grid, where 2 ≤ R ≤ 20. The total number of cells in the grid can be determined by taking a difference of cubes, R3 − (R − 1)3.
N: the maximum number of cells 0x67 can chew through, where 1 ≤ N < R3 − (R − 1)3.
A: the starting cell ID, This cell is located on one of the grid edges: The cell has fewer than six neighbors.
B: the cell ID of the cell containing the honey, where 1 ≤ B ≤ R3 − (R − 1)3.
X: the number of wax-hardened cells, where 0 ≤ X < (R3 − (R − 1)3) − 1.
The second line contains X integers separated by spaces, where each integer is the ID of a wax-hardened cell.
The ID’s, A, B, and all the ID’s on the second line, are distinct positive integers less than or equal to R3 − (R − 1)3.

输出

A single integer K if 0x67 reached the honey at cell B, where B is the Kth cell, otherwise the string No if it was impossible to reach the honey by chewing through N cells or less.

样例输入

6 6 1 45 11
15 16 17 19 26 27 52 53 58 65 74

样例输出

6

提示

 

来源

mcpc2017 

 

题意:是边长为r的五边形,进行编号,从a到b的最短路径是否小于n ,若小于或不存在一条路径,输出No,否则输出最短路径

 

模拟题 ,太心累了,首先建表,也是此题的重点,然后一边bfs,求最小路径即可。

我建表的方法是求出每一个编号的行和列,以及行和列所在的编号

然后找规律,若某点所在的行小于r,可以走的方向为   int updir[6][2]={-1,-1,-1,0,0,-1,0,1,1,0,1,1};

若等于,方向为:int middledir[6][2]={-1,-1,-1,0,0,-1,0,1,-1,-1,1,0};

小于,方向为:int downdir[6][2]={-1,0,-1,1,0,-1,0,1,1,-1,1,0};

 

然后bfs即可

 

c++ code:

#include <bits/stdc++.h>
 
using namespace std;
const int N=2000;
bool vis[N],flag;
struct Node{
    int val,siz; // 编号  步数 
};
struct Map{
    int row,col;// 行 列 
}edge[N];
int mmap[47][47];
int ans=0,n;

int cul(int x){ return x*x*x;}
int downdir[6][2]={-1,0,-1,1,0,-1,0,1,1,-1,1,0};
int middledir[6][2]={-1,-1,-1,0,0,-1,0,1,-1,-1,1,0};
int updir[6][2]={-1,-1,-1,0,0,-1,0,1,1,0,1,1};
int linemax[47];
void init(int r)
{
    int m=cul(r)-cul(r-1);
    //cout<<"m"<<m<<endl;
    for(int i=1;i<=m;i++)
        vis[i]=false;
    int i=1,ant=0,row=1,col=1;
    int n1=r,flag1=0;
    while(i<=m)
    {
        while(ant>=r)
        {
            linemax[row]=col-1;
            row++;
            col=1;
            ant=0;
            if(!flag1)  r++;
            else r--;
            if(r==2*n1-1) flag1=1;
        }
        edge[i].row=row;
        edge[i].col=col;
        mmap[row][col]=i;
        col++;
        ant++;
        i++;
    }
    linemax[row]=col-1;
}
void bfs(int a,int b,int r)
{
    Node p;
    p.val=a;p.siz=0;
    int row,col;
    queue<Node>q;
    if(!vis[a])
        q.push(p);
    vis[a]=true;
    while(!q.empty())
    {
        Node top=q.front();q.pop();
        int val=top.val,siz=top.siz;
       // cout<<val<<" "<<siz<<endl;
        if(val==b)
        {
            if(siz<=n)  flag=true;
            ans=siz;
            return;
        }
        if(edge[val].row<r) //up
        {
            for(int i=0;i<6;i++)
            {
                row=edge[val].row+updir[i][0];
                col=edge[val].col+updir[i][1];
                if(row<1||i>2*r-1||col<1||col>linemax[row]) continue;
                int nowval=mmap[row][col];
                if(!vis[nowval])
                {
                    p.siz=siz+1;
                    p.val=nowval;
                   // cout<<nowval<<" "<<edge[nowval].row<<"^"<<edge[nowval].col<<"*"<<p.siz<<endl;
                    q.push(p);
                    vis[nowval]=true;
                }
            }
        }
        else if(edge[val].row==r) // middle
        {
            for(int i=0;i<6;i++)
            {
                row=edge[val].row+middledir[i][0];
                col=edge[val].col+middledir[i][1];
                if(row<1||i>2*r-1||col<1||col>linemax[row]) continue;
                int nowval=mmap[row][col];
                if(!vis[nowval])
                {
                    p.siz=siz+1;
                    p.val=nowval;
                  //  cout<<nowval<<" "<<edge[nowval].row<<"^"<<edge[nowval].col<<"*"<<p.siz<<endl;
                    q.push(p);
                    vis[nowval]=true;
                }
            }
        }
        else // down
        {
            for(int i=0;i<6;i++)
            {
                row=edge[val].row+downdir[i][0];
                col=edge[val].col+downdir[i][1];
                if(row<1||i>2*r-1||col<1||col>linemax[row]) continue;
                int nowval=mmap[row][col];
                if(!vis[nowval])
                {
                    p.siz=siz+1;
                    p.val=nowval;
                    q.push(p);
                  //  cout<<nowval<<" "<<edge[nowval].row<<"&"<<edge[nowval].col<<"*"<<p.siz<<endl;
                    vis[nowval]=true;
                }
            }
        }
    }
}
int main()
{
    int r,a,b,x,siz;
    flag=false;
    scanf("%d%d%d%d%d",&r,&n,&a,&b,&x);
    init(r);
    while(x--)
    {
        scanf("%d",&siz);
        vis[siz]=true;
    }
    bfs(a,b,r);
    if(flag)
        printf("%d\n",ans);
    else
        puts("No");
    return 0;
}

 

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

java学习day45-Thymeleaf教程(转载)

目录 Thymeleaf 教程 1. 创建模板文件 2. 标准表达式语法 2.1 简单表达式 2.1.1 ${…} 2.1.2 *{…} 2.1.3 #{…} 2.1.4 @{…} 2.1.5 ~{…} 2.1.6 内置对象 2.1.7 工具类 2.2 字面值 2.2.1 文字...

osc_nbg2lo7i
16分钟前
15
0
记录用户登陆信息,你用PHP是如何来实现的

对于初入门的PHP新手来说,或许有一定的难度。建议大家先看看PHP中session的基础含义,需要的朋友可以选择参考。 下面我们就通过具体的代码示例,为大家详细的介绍PHP中session实现记录用户登...

php开源社区
16分钟前
13
0
语音系统源码的开发,一对一语音直播源码

对于大多数人来说,直播已经不再陌生了,所谓是家喻户晓,只要是有智能手机,对于直播肯定是有所了解,对于直播大家想到是娱乐性的互动直播,其实视频直播的话也不是只有这一种方式,还有语音...

qq3595750856
17分钟前
9
0
友链

下面是我的友链啦~~ 外校大佬 _redness 魔法少女 Kylin_Seven 宠辱不惊,闲看庭前花开花落;去留无意,任随天边云卷云舒 Areds 不忘初心,方得使终 Quaint 技术宅拯救世界 校内巨佬们 wxyww ...

osc_94gn551r
18分钟前
5
0
友链

下面是我的友链啦~~ 外校大佬 _redness 魔法少女 Kylin_Seven 宠辱不惊,闲看庭前花开花落;去留无意,任随天边云卷云舒 Areds 不忘初心,方得使终 Quaint 技术宅拯救世界 校内巨佬们 wxyww ...

osc_xih8lf91
19分钟前
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部