首页 > 搜索 > DFS搜索 > HDU 3133-Ye Holy Hand Grenades!-DFS-[解题报告]HOJ
2014
03-03

HDU 3133-Ye Holy Hand Grenades!-DFS-[解题报告]HOJ

Ye Holy Hand Grenades!

问题描述 :

Holy Hand Grenades have found multiple uses throughout history. Most notably, King Arthur did use a Holy Hand Grenade (HHG) to dispatch a vicious rabbit which was guarding the entrance to a cave. The instructions for its use are in the Book of Armaments (Chapter 2, verses 9-21), and are read as follows:

Taunt Exposure Estimation

Unfortunately, the Book of Armaments faileth to mention that the HHG must come to a complete stop (i.e. rest stably) before it can explodeth and blow a rabbit to tiny bits. As long as it rolleth or wobbeleth, it refuseth to explodeth. Unknown is the reason why the authors of the Book of Armaments neglected to mention this pertinent fact. Further complicating matters, different HHGs have different radii of destruction (RD). Once a HHG resteth stably, and explodeth, everything within or equal to its RD shalt be snuffed out. Presumably, this is what happened to the rabbit with big, pointy teeth; however, there remaineth some controversy over this matter. Because of this controversy, the king hath decreed a simulation to be run that may possibly answer this question.

Taunt Exposure Estimation
  • Your task is to determine the result of the grenade’s explosion.
  • The grenade must always be at rest in order to detonate. All HHGs have a radius R=1 and a variable radius of destruction (RD). At the instant of detonation, the rabbit could be mid-leap, on the ground, or underground.
  • For each simulation the terrain remaineth unchanged. It consisteth of two intersecting curves,  y = e-x  and  y = ln(x)  as we have revealed unto you in the illustrious illustration. The curves reside in the plane formed by the rabbit, the grenade, and the center of the earth. The terrain is impervious to detonations, and changeth not between tests.
  • If a bunny’s center of mass is strictly below the ground level (as denoted by the intersecting curves) when a HHG explodeth, that bunny shalt remaineth un-snuffedeth and thus shalt live to bite another day.
  • If the bunny resideth strictly outside of the range of a stably resting HHG’s radius of destruction, that bunny shalt also remain un-snuffedeth out.
  • Each result shalt be dependent upon computations accurate even unto 8 significant figures.
  • There shalt not be an input value smaller even than 1.0E-15 or greater even than 1.0E+15.
  • Because the bunny’s center of mass doth be its location, a bunny might possibly end up inside both the RD and the R=1 of a HHG. This simply means the bunny is curled around the grenade. If the center of mass of such a bunny be strictly inside the RD it shall most surely be snufféd out. Amen.

.

输入:

The first line of input doth contain yea verily a single integer indicating the number of holy hand grenades in the data file. Each line of the file doth contain the radius of destruction of this particular holy hand grenade, and finally doth contain the rabbit’s x coordinate (xb) and y coordinate (yb) during this particular test run.

输出:

The first line of input doth contain yea verily a single integer indicating the number of holy hand grenades in the data file. Each line of the file doth contain the radius of destruction of this particular holy hand grenade, and finally doth contain the rabbit’s x coordinate (xb) and y coordinate (yb) during this particular test run.

样例输入:

2
1.5 3.0 3.0
5.5 3.0 3.0

样例输出:

Bunny Biteth Knights
Bunny Bits

题目链接:http://acm.hit.edu.cn/hoj/problem/view?id=3133

简单的搜索题。

输出白盒测试的基本路径。注意题目中关于基本路径的定义。。。

考虑到有可能(不知有没有可能)标号和数量不符的情况,离散化一下。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stack>
#include <queue>
#include <map>
#include <algorithm>
#include <iostream>
using namespace std;

#define Maxn 30
#define Maxm 2005

struct Point
{
    int vis;
    int lchild,rchild;
    int child;
    
}point[Maxn];

int vis[Maxn];
int ma[Maxn][Maxn];

vector <int> v[Maxm];
int vnum = 0;
map <int,int> just;
map <int,int> to;

bool cmp(vector<int> a,vector<int> b)
{
    if(a.size() == b.size())
    {
        for(int i=0;i<a.size();i++)
        {
            if(a[i]!=b[i]) return a[i]<b[i];
        }    
    }
    else return a.size() < b.size();
}
void print(vector<int> has)
{
    int flag = 1;
    for(int i = has.size()-1;i>0;i--)
    {
        flag = flag & ma[has[i]][has[i-1]];
        ma[has[i]][has[i-1]] = 1;
    }
    if(flag) return;
    for(int i=0;i<has.size();i++)
    {
        v[vnum].push_back(to[has[i]]);
    }
    vnum++;
}
void dfs(int s,vector<int> has)
{
    if(point[s].vis == 0)
    {
        point[s].vis = 1;
        if(point[s].rchild!=-1 && point[s].lchild!=-1)
        {
            vector<int> t1 = has;
            t1.push_back(point[s].rchild);
            dfs(point[s].rchild,t1);
            vector<int> t2 = has;
            t2.push_back(point[s].lchild);
            dfs(point[s].lchild,t2);
        }
        else if(point[s].child!=-1)
        {
            vector<int> t3 = has;
            t3.push_back(point[s].child);
            dfs(point[s].child,t3);
        }
        else print(has);
        point[s].vis = 0;
    }
    else print(has);
}

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
    #endif
    int s;
    char str[20];
    int a,b;
    char d;
    while(scanf(" %d",&s)!=EOF)
    {
        for(int i=0;i<Maxn;i++)
        {
            point[i].vis = 0;
            point[i].lchild = point[i].rchild = point[i].child = -1;
        }
        memset(ma,0,sizeof(ma));
        for(int i=0;i<Maxm;i++)
        {
            v[i].clear();
        }
        vnum = 0;
        just.clear();
        to.clear();
        int hh = 0;
        if(just.find(s) == just.end()) just[s] = ++hh;
        to[just[s]] = s;
        s = just[s];
        while(scanf(" %s",str)!=EOF && str[0]!='E')
        {
            sscanf(str,"%d->%d,%c",&a,&b,&d);
            if(just.find(a) == just.end()) just[a] = ++hh;
            if(just.find(b) == just.end()) just[b] = ++hh;
            to[just[a]] = a;
            a = just[a];
            to[just[b]] = b;
            b = just[b];
            if(d == 'T') point[a].lchild = b;
            else if(d == 'F') point[a].rchild = b;
            else point[a].child = b;
        }
        vector <int> has;
        has.push_back(s);
        dfs(s,has);
        sort(v,v+vnum,cmp);
        printf("CC=%d\n",vnum);
        for(int i=0;i<vnum;i++)
        {
            for(int j=0;j<v[i].size();j++)
            {
                if(j == v[i].size()-1) printf("%d\n",v[i][j]);
                else printf("%d,",v[i][j]);
            }
        }
    }
    return 0;
}

参考:http://blog.csdn.net/niuox/article/details/10414811


,
  1. 漂亮。佩服。
    P.S. unsigned 应该去掉。换行符是n 不是/n
    还可以稍微优化一下,
    int main() {
    int m,n,ai,aj,bi,bj,ak,bk;
    while (scanf("%d%d",&m,&n)!=EOF) {
    ai = sqrt(m-1);
    bi = sqrt(n-1);
    aj = (m-ai*ai-1)>>1;
    bj = (n-bi*bi-1)>>1;
    ak = ((ai+1)*(ai+1)-m)>>1;
    bk = ((bi+1)*(bi+1)-n)>>1;
    printf("%dn",abs(ai-bi)+abs(aj-bj)+abs(ak-bk));
    }
    }

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  3. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥