Untitled

mail@pastecode.io avatarunknown
plain_text
a month ago
3.3 kB
2
Indexable
Never
#include <iostream>
#include <set>
 
using namespace std;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
struct Result
{
    int row;
    int col;
};
 
struct Bacteria
{
    int id;
    int size;
    int time;
};
struct node{
    int r,c,l;
} node[40000];  
 
struct cmp{
    bool operator() (int x,int y){
        return (node[x].l<node[y].l);
    }
};
int map[201][201];
int vis[201][201];
int d_time[3005];
int size;
int cnt_node;
int cnt_bac;
 
set<int, cmp> s;
 
void init(int N)
{
    size=N;
    cnt_bac=0;
    cnt_node=0;
    for(int i=0;i<3005;i++){
        d_time[i]=0;
    }
    for(int i=1; i<201;i++){
        for(int j=1;j<201;j++){
            map[i][j]=0;
            vis[i][j]=0;
        }
    }
}
 
int qx[40000];
int qy[40000];
int f,r;
 
void push(int x, int y){
    r++;
    qx[r]=x;
    qy[r]=y;
}
void pop(int &x,int &y){
    f++;
    x=qx[f];
    y=qy[f];
}
 
 
bool check(int ro, int c,int num,int t){
    int id=map[ro][c];
    if(id!=0&&d_time[id]>t) return false;
    cnt_bac++;
    f=r=-1;
    push(ro, c);
    vis[ro][c]=cnt_bac;
    num--;
    int x,y;
    while(f!=r){
        pop(x,y);
        for(int i=0;i<4;i++){
            int xx=x+dx[i];
            int yy=y+dy[i];
            if(xx>0&&xx<=size&&yy>0&&yy<=size){
                if(map[xx][yy]!=0&&d_time[map[xx][yy]]<=t) map[xx][yy]=0;
                if(vis[xx][yy]<cnt_bac&&map[xx][yy]==0){
                    push(xx,yy);
                    num--;
                    vis[xx][yy]=cnt_bac;
                    if(num==0) return true;
                }
            }
        }
    }
    return false;
}
Result putBacteria(int mTime, int mRow, int mCol, Bacteria mBac)
{
    Result ret = { 0, 0 };
    if(!check(mRow,mCol,mBac.size,mTime)) return ret;
    cnt_node=0;
    s.clear();
    node[cnt_node].r=mRow;
    node[cnt_node].c=mCol;
    node[cnt_node].l=0;
    s.insert(cnt_node);
    cnt_node++;
    d_time[mBac.id]=mTime+mBac.time;
    cnt_bac++;
    while(mBac.size>0){
        int idx=*(s.begin());
        s.erase(s.begin());
        map[node[idx].r][node[idx].c]=mBac.id;
        mBac.size--;
        if(mBac.size==0) {
            ret.row=node[idx].r;
            ret.col=node[idx].c;
        }
        for(int i=0;i<4;i++){
            int xx=node[idx].r+dx[i];
            int yy=node[idx].c+dy[i];
            if(xx>0&&xx<=size&&yy>0&&yy<=size){
                if(map[xx][yy]!=0&&d_time[map[xx][yy]]<=mTime) map[xx][yy]=0;
                if(vis[xx][yy]<cnt_bac&&map[xx][yy]==0){
                    vis[xx][yy]=cnt_bac;
                    node[cnt_node].r=xx;
                    node[cnt_node].c=yy;
                    node[cnt_node].l=(abs(xx-mRow)+abs(yy-mCol))*10000+xx*100+yy;
                    s.insert(cnt_node);
                    cnt_node++;
                }
            }
        }
    }
    return ret;
}
 
int killBacteria(int mTime, int mRow, int mCol)
{
    int id=map[mRow][mCol];
    if(id==0) return 0;
    if(d_time[id]<=mTime) return 0;
    d_time[id]=0;
    return id;
}
 
int checkCell(int mTime, int mRow, int mCol)
{
    int id=map[mRow][mCol];
    if(id==0) return 0;
    if(d_time[id]<=mTime) return 0;
    return id;
}