洛谷 P3072 [USACO13FEB]Perimeter S(dfs)

洛谷 P3072 [USACO13FEB]Perimeter S(dfs) 

题目保证所有的草堆构成连通块,我们可以用 dfs 很简单的获得各个草堆的相对位置

洛谷 P3072 [USACO13FEB]Perimeter S(dfs) 

如上图所示,白色的方块为草堆的位置,那么他的外周长是绿色的方块个数,其中红色方块个数的贡献是二,也就是说绕着外周长的外面走一圈,看看当前方格挨着几个草堆,这样通过 dfs 就可以将问题解决了。

遍历所有的绿色/红色方块一次且仅以此,搜索到白色那么 ans+1,此方块的任务结束

const int N=2e5+5;
 
    int n,m;
    int i,j,k;
    //int a[N];
    set<pii> all;
    map<pii,int> vis;
    int ans=0;

bool judge(int x,int y)
{
    for(int i=-1;i<=1;i++){
        for(int j=-1;j<=1;j++){
            if(i==0 && j==0) continue;
            if(all.count(mp(x+i,y+j))) return true;
        }
    }
    return false;
}

void dfs(int x,int y)
{
    if(all.count(mp(x,y))){ ans++; return ; }
    if(vis[mp(x,y)]==1) return ;
    else vis[mp(x,y)]=1;
    if(judge(x,y)==false) return ;
    for(int i=0;i<4;i++) dfs(x+dx[i],y+dy[i]);
}

int main()
{
    while(~sd(n)){
        int x,y;
        int maxx=0,maxy=0;
        while(n--){
            sdd(x,y);
            all.insert(mp(x,y));
            if(y>maxy){
                maxy=y;
                maxx=x;
            }
        }
        dfs(maxx,maxy+1);
        pd(ans);
    }
    return 0;
}

 

上一篇:Codeforces Round #753 (Div. 3) 题解


下一篇:CF1393B Applejack and Storages 题解