Untitled
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; }