hiho 1613 - 墨水滴 - bfs+优先队列 *

题目链接

小Ho有一张白纸，上面有NxN个格子。小Ho可以选择一个格子(X, Y)，在上面滴一滴墨水。如果这滴墨水的颜色深度是G，那么这个格子也会被染成深度为G的格子。同时周围的格子也会被这滴墨水浸染，不过颜色深度会略微降低。具体来说，如果一个格子距离(X, Y)的曼哈顿距离是D，那么它会被染成深度为max{0, G-D}的格子。

例如在(3, 3)滴一滴颜色深度为10的墨水，则(2, 3)(4, 3)(3, 2)(3, 4)四个格子会被染成深度为9，(1, 3)(2, 2)(2, 3)(3, 1)(3, 5)(4, 2)(4, 4)(5, 3)会被染成深度为8……

现在小Ho在K个格子中都滴了一滴墨水。于是一个格子可能被多滴墨水浸染，这时它的颜色深度是单滴墨水浸染时最高的颜色深度。

给定K滴墨水的位置和颜色深度，你能帮小Ho算出最后整张白纸上所有格子的颜色深度吗？

输入

第一行包含两个整数N和K。

以下K行每行包含三个整数X_i, Y_i和G_i。

对于30%的数据, 1 ≤ N, K ≤ 100

对于100%的数据，1 ≤ N ≤ 1000 1 ≤ K ≤ 10000 0 ≤ X_i, Y_i < N 0 ≤ G_i < 2048

输出

输出一个NxN的矩阵，代表每个格子最终的颜色深度

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <queue>

using namespace std;

struct Node{

    int x,y;

    int depth;

    Node(){};

    Node(int x,int y,int depth):x(x),y(y),depth(depth){};

    bool operator<(const Node& another) const{

        return this->depth<another.depth;

    }

};

const int N = 1024;

const int skip[4][2]={{0,1},{0,-1},{1,0},{-1,0}};

int A[N][N];

priority_queue<Node> q;

int main(){

    int n,t; cin>>n>>t;

    while(t--){

        int x,y,d;

        scanf("%d%d%d",&x,&y,&d);

        q.push(Node(x,y,d));

    }

    memset(A,0,sizeof(A));

    while(!q.empty()){

        Node cur = q.top(); q.pop();

        if(cur.depth<=A[cur.x][cur.y]) continue;

        A[cur.x][cur.y]=cur.depth;

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

            int tx = cur.x + skip[i][0];

            int ty = cur.y + skip[i][1];

            if(tx<0||ty<0||tx>=n||ty>=n) continue;

            if(cur.depth-1>A[tx][ty]){

                q.push(Node(tx,ty,cur.depth-1));

            }

        }

    }

    for(int i=0;i<n;i++){

        for(int j=0;j<n;j++) printf("%d ",A[i][j]); puts("");

    }

    return 0;

}

巴特西

hiho 1613 - 墨水滴 - bfs+优先队列 *

输入

输出

最新文章

热门文章