补题：HNU暑期训练第一场第三题——Ninja Map

谁践踏了优雅 2022-05-18 02:36 183阅读 0赞

题目链接：  
[Ninja Map][]

题目大意：给定n行n列条垂直交错的直线，形成n\*n个交点（编号：1~n\*n），给出各交点之间的相邻关系，求出任意一个符合该相邻关系的图

解题思路：  
通过各交点度的关系，最外一层的交点度为2或3，根据这个关系从度为2的一点出发，dfs遍历，求出最外一层，然后对求出的交点的相邻点度数依次减一，从而我们可以继续循环求出第二层（即当前的最外层），记录每个交点处于第几层，先把第一行存入二维数组，然后根据每个位置所属层数，以及相邻关系，求出剩下的行。

AC代码如下：

#include <iostream>
    #include <vector>
    #include <cstdio>
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    
    
    using namespace std;
    
    vector<int> edge[10005],ret;
    int ans[105][105],du[10005],vis[10005],deep[10005],vis2[10005];
    int n,cnt,s,temp,d;
    
    void init(){
        memset(ans, 0, sizeof(ans));
        memset(du, 0, sizeof(du));
        memset(vis, 0, sizeof(vis));
        memset(vis2, 0, sizeof(vis2));
        memset(deep, -1, sizeof(deep));
        for(int i=0; i<=10000; ++i) edge[i].clear();
        cnt = 0; d = 0;
    }
    
    void dfs(int u){
        vis[u]=1;
        ret.push_back(u);
        deep[u] = d;
        temp++; cnt++;
        int sz = edge[u].size();
        for(int j=0; j<sz; ++j){
            int v = edge[u][j];
            if((du[v]==2 ||du[v]==3) && !vis[v]){
                dfs(v);
            }
        }
    }
    
    void solve(){
        while(1){
            for(int i=1; i<=n*n; ++i){
                if((du[i]==2||du[i]==0)&&!vis[i]) {
                    s=i;
                    break;
                }
            }
            temp=0;
            dfs(s);
            int len=ret.size();
            for(int i=1; i<=temp; ++i){
                int u=ret[len-i];
                for(int j=0; j<edge[u].size(); ++j){
                    du[edge[u][j]]--;
                }
            }
            d++;
    
            if(cnt>=n*n) break;
        }
    
        for(int j=0; j<n; ++j){
            ans[0][j]=ret[j];
            vis2[ret[j]]=1;
        }
    
        for(int i=1; i<n; ++i){
            for(int j=0; j<n; ++j){
                int dd=min(j,n-1-j);
                dd=min(dd,n-1-i);
                dd=min(dd,i);
                for(int k=0; k<edge[ans[i-1][j]].size(); ++k){
                    int v = edge[ans[i-1][j]][k];
                    if(!vis2[v] && deep[v]==dd) {
                        ans[i][j]=v;
                        vis2[v]=1;
                    }
                }
            }
        }
    
    
        for(int i=0; i<n; ++i){
            int j;
            for(j=0; j<n-1; ++j){
                printf("%d ",ans[i][j]);
            }
            printf("%d",ans[i][j]);
            if(i<n-1) printf("\n");
        }
    }
    
    int main(){
        init();
        scanf("%d",&n);
        int u,v;
        for(int i=0; i<(2*n*n-(2*n)); ++i){
            scanf("%d%d",&u,&v);
            edge[u].push_back(v);
            edge[v].push_back(u);
            du[u]++; du[v]++;
        }
        solve(); 
        return 0;
    }

[Ninja Map]: http://acm.hnu.cn/online/?action=problem&type=show&id=14106&courseid=394