HDU 5336 XYZ and Drops 2015 Multi-University Training Contest 4 1010

这题的题意是给你一幅图，图里面有水滴。每一个水滴都有质量，然后再给你一个起点，他会在一開始的时候向四周发射4个小水滴，假设小水滴撞上水滴，那么他们会融合，假设质量大于4了，那么就会爆炸，向四周射出质量为一的水滴，问你在T时刻的时候，各个水滴的状态。

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <math.h>

#include <queue>

#define maxn 1000000

#define inf (1e9 + 5)

#define mem(a, b) memset(a, b, sizeof(a))

using namespace std;

int n, m, nn, T, ox[4] = {-1, 0, 1, 0}, oy[4] = {0, -1, 0, 1}, sx, sy;

int vis[105][105];

bool vis2[105];

struct node

{

    int x, y, sizes, dis, dir;//坐标，质量，（距离）时间，方向。

}nd[105];

struct anss

{

    int a, sizes, t = -1;

}ans[105];

void bfs()

{

    queue<struct node> q;

    struct node tt;

    tt.x = sx;

    tt.y = sy;

    tt.dis = 0;

    for(int i = 0;i < 4;i++)//起始的四个方向

        tt.dir = i, q.push(tt);

    mem(vis2, 0);

    int dd = 0;

    while(!q.empty())

    {

        struct node tmp = q.front();

        q.pop();

        if(tmp.dis > dd)//假设进入下一层，被引爆的水滴质量为0

        {

            for(int i = 1;i <= nn;i++)

                if(vis2[i])

                    nd[i].sizes = 0;

            mem(vis2, 0);

            dd++;

        }

        if(tmp.dis + 1 > T)//假设时间大于T就不继续

            continue;

        int tmpx = tmp.x + ox[tmp.dir];

        int tmpy = tmp.y + oy[tmp.dir];

        if(tmpx <= 0||tmpx > n||tmpy <= 0||tmpy > m)//超出map

            continue;

        if(nd[vis[tmpx][tmpy]].sizes)//假设这个点有水滴

        {

            if(nd[vis[tmpx][tmpy]].sizes <= 3)//质量不会被引爆的时候

            {

                ans[vis[tmpx][tmpy]].a = 1;

                ans[vis[tmpx][tmpy]].sizes = nd[vis[tmpx][tmpy]].sizes + 1;

                ans[vis[tmpx][tmpy]].t = tmp.dis + 1;

                nd[vis[tmpx][tmpy]].sizes += 1;

            }

            else if(nd[vis[tmpx][tmpy]].sizes > 3)//质量会被引爆的时候

            {

                ans[vis[tmpx][tmpy]].a = 0;

                ans[vis[tmpx][tmpy]].sizes = nd[vis[tmpx][tmpy]].sizes + 1;

                ans[vis[tmpx][tmpy]].t = tmp.dis + 1;

                nd[vis[tmpx][tmpy]].sizes = 5;

                if(!vis2[vis[tmpx][tmpy]])

                {

                    vis2[vis[tmpx][tmpy]] = 1;

                    struct node jj;

                    jj.x = tmpx, jj.y = tmpy, jj.dis = tmp.dis + 1;

                    for(int i = 0;i < 4;i++)

                        jj.dir = i, q.push(jj);

                }

            }

        }

        else//没有水滴，继续按原方向射出

        {

            struct node jj;

            jj.x = tmpx, jj.y = tmpy, jj.dis = tmp.dis + 1, jj.dir = tmp.dir;

            q.push(jj);

        }

    }

}

int main()

{

    while(~scanf("%d%d%d%d", &n, &m, &nn, &T))

    {

        mem(vis, 0);

        mem(ans, -1);

        for(int i = 1;i <= nn;i++)

            scanf("%d%d%d", &nd[i].x, &nd[i].y, &nd[i].sizes), vis[nd[i].x][nd[i].y] = i;

        scanf("%d%d", &sx, &sy);

        bfs();

        for(int i = 1;i <= nn;i++)

        {

            if(ans[i].t != -1)

            {

                if(ans[i].a)

                    printf("%d %d\n", ans[i].a, ans[i].sizes);

                else

                    printf("%d %d\n", ans[i].a, ans[i].t);

            }

            else

                printf("1 %d\n", nd[i].sizes);

        }

    }

    return 0;

}