bfs-hdu3533-escape+生日礼物（堆）-牛客

Escape (BFS) -hdu 3533

题意：一个人从（0,0）跑到(n,m),只有d点能量，一秒消耗一点，在图中有k个塔，给出塔的射击方向c，射击周期t，子弹速度v，坐标x,y。问这个人能不能安全到达终点

解：搜索，注意bool和int卡内存；人可以选择停止不动

当人位于某一个点，塔都是对这人的方向进行射击，看子弹是否刚好位于人的这个坐标(可以剪枝）标记数组需要三维visx[t]对于每一个t只能由一个对应的坐标。对人当前位置的四个方向进行处理。

代码：

#include <bits/stdc++.h>
using namespace std;
int n,m,k,d;
int dir[5][2] = {0,1,1,0,0,-1,-1,0,0,0};
bool vis[105][105][1005];
 
struct period
{
    char c;
    int t,v;
} s[105][105];
 
struct node
{
    int x,y,step;
};
 
int check(int x,int y)
{
    if(x<0 || x>n || y<0 || y>m)
        return 0;
    return 1;
}
 
void bfs()
{
    node a,next;
    queue<node> Q;
    int i,j,flag,dis,tem;
    a.x = a.y = a.step = 0;
    Q.push(a);
    vis[0][0][0] = true;
    while(!Q.empty())
    {
        a = Q.front();
        Q.pop();
          if(a.step>d)
            break;
        if(a.x == n && a.y == m)
        {
            printf("%d
",a.step);
            return ;
        }
        for(i = 0; i<5; i++)
        {
            next = a;
            next.x+=dir[i][0];
            next.y+=dir[i][1];
            next.step++;
            if(!check(next.x,next.y)) continue;
            if(!s[next.x][next.y].t && !vis[next.x][next.y][next.step] && next.step<=d)
            {
                flag = 1;
                for(j = next.x-1; j>=0; j--)
                {
                    if(s[j][next.y].t && s[j][next.y].c == 'S')
                    {
                        dis = next.x-j;
                        if(dis%s[j][next.y].v) break;
                        tem = next.step-dis/s[j][next.y].v;
                        if(tem<0) break;
                        if(tem%s[j][next.y].t==0)
                        {
                            flag = 0;
                            break;
                        }
                    }
                    if(s[j][next.y].t)
                        break;
                }
                if(!flag)
                    continue;
                for(j = next.x+1; j<=n; j++)
                {
                    if(s[j][next.y].t && s[j][next.y].c == 'N')
                    {
                        dis = j-next.x;
                        if(dis%s[j][next.y].v) break;
                        tem = next.step-dis/s[j][next.y].v;
                        if(tem<0) break;
                        if(tem%s[j][next.y].t==0)
                        {
                            flag = 0;
                            break;
                        }
                    }
                    if(s[j][next.y].t)
                        break;
                }
                if(!flag)
                    continue;
                for(j = next.y-1; j>=0; j--)
                {
                    if(s[next.x][j].t && s[next.x][j].c == 'E')
                    {
                        dis = next.y-j;
                        if(dis%s[next.x][j].v) break;
                        tem = next.step-dis/s[next.x][j].v;
                        if(tem<0) break;
                        if(tem%s[next.x][j].t==0)
                        {
                            flag = 0;
                            break;
                        }
                    }
                    if(s[next.x][j].t)
                        break;
                }
                if(!flag)
                    continue;
                for(j = next.y+1; j<=m; j++)
                {
                    if(s[next.x][j].t && s[next.x][j].c == 'W')
                    {
                        dis = j-next.y;
                        if(dis%s[next.x][j].v) break;
                        tem = next.step-dis/s[next.x][j].v;
                        if(tem<0) break;
                        if(tem%s[next.x][j].t==0)
                        {
                            flag = 0;
                            break;
                        }
                    }
                    if(s[next.x][j].t)
                        break;
                }
                if(!flag)
                    continue;
                vis[next.x][next.y][next.step] =true;
                Q.push(next);
            }
        }
    }
    printf("Bad luck!
");
}
 
int main()
{
    int i,j,x,y,t,v;
    char str;
    while(~scanf("%d%d%d%d",&n,&m,&k,&d))
    {
        memset(s,0,sizeof(s));
        memset(vis,false,sizeof(vis));
        for(i = 0; i<k; i++)
        {
            cin>>str>>t>>v>>x>>y;
            s[x][y].v = v;
            s[x][y].t = t;
            s[x][y].c = str;
        }
        bfs();
    }
 
    return 0;}

生日礼物（堆）scoi2009

题意：小西有一条很长的彩带，彩带上挂着各式各样的彩珠。已知彩珠有N个，分为K种。简单的说，可以将彩带考虑为x轴，每一个彩珠有一个对应的坐标(即位置)。某些坐标上可以没有彩珠，但多个彩珠也可以出现在同一个位置上。小布生日快到了，于是小西打算剪一段彩带送给小布。为了让礼物彩带足够漂亮，小西希望这一段彩带中能包含所有种类的彩珠。同时，为了方便，小西希望这段彩带尽可能短，你能帮助小西吗。

解：用堆维护彩带的左边，右边就是堆中的最大值，题目要求每种都要有，。所以先将每种求由大到小排个序，每次删除顶堆，并且插入一个与删除元素相同种的球。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e2+10;
const int mod=142857;
const int inf=0x3f3f3f3f;
typedef long long ll;
typedef pair<int,int> pii;
pii a[maxn];
int cnt,f[maxn],sum;
int n,k;
int ans=inf;
priority_queue<pii,vector<pii>,greater<pii> >Q;
int main()
{
    cin>>n>>k;
    for(int i=1; i<=k; i++)
    {
        int t;
        cin>>t;
        for(int j=1; j<=t; j++)
        {
            int x;
            cin>>x;
            a[cnt+j]=make_pair(x,i);
        }
        cnt+=t;
    }
    sort(a+1,a+1+n);
    for(int i=1; i<=n; i++)
    {
        Q.push(a[i]);
        if(!f[a[i].second]) sum++;
        f[a[i].second]=a[i].first;
        while(f[Q.top().second]!=Q.top().first) Q.pop();
        if(sum==k)
        ans=min(ans,a[i].first-Q.top().first);
    }
    
    cout<<ans<<endl;
    system("pause");
}