首页 > 代码库 > UVALive 3977 BFS染色

UVALive 3977 BFS染色

2024-07-12 15:36:32   223人阅读

这个题意搞了半天才搞明白 就是如果定义一个d-summit，即从该点到另一个更高的点，经过的路径必定是比当前点低至少d高度的，如果该点是最高点，没有比他更高的，就直接视为顶点 其实就是个BFS染色，先按降序排序，然后每个点对其可到达的点染色，h-d的点为边界，走到这里就不用往下染了 然后其他店染色的时候若产生冲突，则非d—summit,否则该点为顶点 今天还有COJ上一个BFS染色的题目，一直TLE。。。还没弄出来

 

#include <iostream>#include <cstdio>#include <cstring>#include <queue>#include <algorithm>using namespace std;int mat[510][510];int n,m,d,cnt;struct node{    int x,y,h;    bool operator <(const node& rhs)const{        return h>rhs.h;    }}P[510*500];int dir[][2]={{0,1},{0,-1},{1,0},{-1,0}};int vis[510][510];int ans;inline void bfs(int x){    node a=P[x];    int flag=1;    int tot=1;    if (vis[a.x][a.y]!=-1){        flag=0;        return;    }    else vis[a.x][a.y]=a.h;    queue<node> q;    q.push(a);    int sh=a.h;    int lh=a.h-d;    while (!q.empty())    {        node u=q.front();        q.pop();        for (int i=0;i<4;i++){            node np;            np.x=u.x+dir[i][0];            np.y=u.y+dir[i][1];            np.h=mat[np.x][np.y];            if (np.x>=n || np.y>=m || np.x<0 ||np.y<0) continue;            if (np.h<=lh) continue;            if (vis[np.x][np.y]!=-1){                if (vis[np.x][np.y]!=sh) flag=0;                continue;            }            vis[np.x][np.y]=sh;            if (np.h==sh) tot++;            q.push(np);        }    }    if (flag==1) ans+=tot;}int main(){    int t;    scanf("%d",&t);    while (t--)    {        cnt=0;        scanf("%d%d%d",&n,&m,&d);        for (int i=0;i<n;i++)        {            for (int j=0;j<m;j++){                scanf("%d",&mat[i][j]);                P[cnt].x=i;                P[cnt].y=j;                P[cnt++].h=mat[i][j];            }        }        sort(P,P+n*m);        memset(vis,-1,sizeof vis);        ans=0;        for (int i=0;i<n*m;i++)        {            bfs(i);        }        printf("%d\n",ans);    }    return 0;}

　　


联系
我们