XDOJ_1089_bfs+优先队列

http://acm.xidian.edu.cn/problem.php?id=1089

按时间bfs+优先队列,注意水珠一起到达一点炸开的情况。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;

int n,m,nn,tt,a[105][2],sta[105][105],t[105][105],dir[4][2] = {-1,0,0,-1,1,0,0,1};
struct water
{
    int x,y,d,t;
    water(int _x,int _y,int _d,int _t):x(_x),y(_y),d(_d),t(_t){};
    friend bool operator <(water X,water Y)
    {
        return X.t > Y.t;
    }
};

void bfs(int x,int y)
{
    priority_queue<water> q;
    q.push(water(x,y,0,1));
    q.push(water(x,y,1,1));
    q.push(water(x,y,2,1));
    q.push(water(x,y,3,1));
    while(!q.empty())
    {
        water temp = q.top();
        q.pop();
        if(temp.t > tt) return;
        int xx = temp.x+dir[temp.d][0],yy = temp.y+dir[temp.d][1];
        if(xx < 1 || xx > n || yy < 1 || yy > m)    continue;
        if(t[xx][yy] == temp.t)    continue;
        if(sta[xx][yy] == 0)  q.push(water(xx,yy,temp.d,temp.t+1));
        else if(sta[xx][yy] == 4)
        {
            sta[xx][yy] = 0;
            t[xx][yy] = temp.t;
            q.push(water(xx,yy,0,temp.t+1));
            q.push(water(xx,yy,1,temp.t+1));
            q.push(water(xx,yy,2,temp.t+1));
            q.push(water(xx,yy,3,temp.t+1));
        }
        else    sta[xx][yy]++;
    }
}

int main()
{
    while(~scanf("%d%d%d%d",&n,&m,&nn,&tt))
    {
        memset(sta,0,sizeof(sta));
        memset(t,0,sizeof(t));
        for(int i = 1;i <= nn;i++)
        {
            int x;
            scanf("%d%d%d",&a[i][0],&a[i][1],&x);
            sta[a[i][0]][a[i][1]] = x;
        }
        int x,y;
        scanf("%d%d",&x,&y);
        bfs(x,y);
        for(int i = 1;i <= nn;i++)
        {
            if(t[a[i][0]][a[i][1]] == 0)    printf("1 %d\n",sta[a[i][0]][a[i][1]]);
            else    printf("0 %d\n",t[a[i][0]][a[i][1]]);
        }
    }
    return 0;
}
时间: 11-12

XDOJ_1089_bfs+优先队列的相关文章

51nod1428(优先队列)

题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1428 题意:中文题诶- 思路:贪心 问最少要多少教室就是求最多有多少个时间段产生了交集咯.我们先用结构体存储区间并将其按照左端点升序排列,若左端点相同则按右端点升序排列. 接下来遍历所有区间,并维护一个优先队列,其中存储区间右端点值.对于当前区间,我们将优先队列中所有比当前区间左端点小的元素删除(因为其所在区间不会与当前区间相交嘛),然后再将当前区间的右端点加

优先队列实现哈弗曼最小权值

建立哈弗曼树要求我们每次都选频率权值最小的点构成节点,即权值小的点在树的深处,权值大的点在树的浅处,根据节点选择的特点,我们可以把节点的值放在优先队列中,包括新形成的节点. 我们先定义优先队列的优先级别. 1 struct cmp 2 { 3 bool operator()(const int &a,const int &b) 4 { 5 return a>b; 6 } 7 };//最小值优先出队 然后就是实现的整个程序. #include<stdio.h> #inclu

NYOJ 284 坦克大战 &amp;&amp; POJ 2312 Battle City (广搜+优先队列)

链接:click here~~ 题意: 描述 Many of us had played the game "Battle city" in our childhood, and some people (like me) even often play it on computer now. What we are discussing is a simple edition of this game. Given a map that consists of empty space

hdu 4006 The kth great number(优先队列)

The kth great number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65768/65768 K (Java/Others) Total Submission(s): 6982    Accepted Submission(s): 2837 Problem Description Xiao Ming and Xiao Bao are playing a simple Numbers game. In a roun

优先队列(堆)

一.优先队列的一些简单的实现: 1. 使用一个简单的链表在表头以O(1) 执行插入操作,并遍历该链表以删除最小元,这需要O(N) 的时间. 2. 始终让表保持有序状态:这使得插入代价高昂(O(N)), 而删除代价低廉(O(1)).基于删除最小元的操作从不多于插入操作的事实,因此,前者是更好地想法. 3. 使用二叉查找树,它对这两种操作的平均运行时间是O(logN).尽管插入是随机的,而删除不是,但这个结论还是成立的.由于删除的唯一元素是最小元.反复除去左子树中的节点似乎损害树的平衡,使得右子树加

优先队列比较符重载

#include <iostream> #include <queue> using namespace std; struct Node{ int x, y; friend bool operator<(Node a, Node b){ return a.x > b.x; //x最小的节点在队首 } }; int main(){ priority_queue<Node> PQ; Node temp = {2, 3}; PQ.push(temp); temp

[ACM] hdu 1242 Rescue (BFS+优先队列)

Rescue Problem Description Angel was caught by the MOLIGPY! He was put in prison by Moligpy. The prison is described as a N * M (N, M <= 200) matrix. There are WALLs, ROADs, and GUARDs in the prison. Angel's friends want to save Angel. Their task is:

1475 建设国家(优先队列)

1475 建设国家 基准时间限制:1 秒 空间限制:131072 KB 分值: 20 难度:3级算法题 小C现在想建设一个国家.这个国家中有一个首都,然后有若干个中间站,还有若干个城市. 现在小C想把国家建造成这样的形状:选若干(可以是0个)的中间站把他们连成一条直线,然后把首都(首都也是一个中间站)连在这一条直线的左端.然后每个点可以连一个城市,特别的是最右端的点可以连接两个城市. 现在有n个城市的规划供小C选择.但是,他们那儿的交通条件比较差,他们那儿一天是2*H个小时,每个城市里面的人每天

Battle City BFS+优先队列

Battle City Many of us had played the game "Battle city" in our childhood, and some people (like me) even often play it on computer now. What we are discussing is a simple edition of this game. Given a map that consists of empty spaces, rivers,