/ phigros / 题库 /

流浪地球2-月球支线

流浪地球2-月球支线

暂无测试数据。

题目背景

月球危机应对方案分为三步,
第一步,把全球核武器用空间站运抵月球,以相控阵方式,布设在直径四十六公里的坎帕努斯环形山。
第二步,串联全球核武器,以空间为中继卫星遥控引爆,引发月核聚变,使月球自行坍缩瓦解。
第三步,重启杜勒斯、东京、北京三地根服务器,恢复全球互联网,启动全球行星发动机,逃离月球残骸,踏上新征程。

彻底毁掉月球的能量,是全球核武总当量的十亿倍。我们目前集结的核弹总量,连根引线都算不上!所以,布设位置一定要精确,确保相控阵阵元聚焦点准确。

题目描述

在布设月球核弹前,对于地质的勘测必不可少,请你编写程序,辅助550W/moss进行对月球坎帕努斯环形山地质勘测结果的计算,得到各个位置是否能布设核弹。

输入格式

第一行两个整数x和z,由一个空格隔开
接下来有x * z行,每行x个数字,表示矿物的种类,其中,-1表示空腔,空腔上方不能布设核弹,x * x * z个数字中,每x * x个数字为一组,共z组,表示由下至上z层地质勘测结果。
第x * z + 1行有一个整数n
接下来有n行,每行有两个数字a和b,之间由一个空格隔开,表示在与a矿物空间曼哈顿距离≤b的位置里无法布设核弹
再接下来有一个整数m,下一行有m个整数,由一个空格隔开,表示危险的矿物,要进行计数。矿物群:有一角或一棱相邻的矿物块均属于同一矿物群。

输出格式

为了减小输出文件,使550W/moss算力集中在破译密码,因此前两行每行有x个正整数,由一个空格隔开,表示的是可布设核弹图的深度优先搜索遍历和宽度优先搜索遍历,可布设核弹图是一个x * x的01矩阵,在此我们将其看作一个邻接矩阵,1表示可布设核弹,0表示不可布设核弹。
接下来有m行,每行k个整数,表示第m种危险的矿物群的数量,为确定答案的唯一性,请输出升序排列的k个整数,两两由一个空格隔开。

输入输出样例明天做

数据范围

x≤100,z≤50,保证地址勘测输入图的每个数字的绝对值都≤20,n≤10,m≤10

//先把没写完的代码挂在这,供同学参考
#include<bits/stdc++.h>
using namespace std;
struct CannotLayout
{
    int MineralType,DangerousDistances;
    int SumCoordinate=0;
    struct CannotMineralCoordinate
    {
        int Abscissa,Ordinate,Vertical;
    }MineralCoordinate[500005];
}Cannot[15];
struct Dangerous
{
    int DangerousMineral,SumMineral=0;
    int MineralGroup[500005];
}Danger[15];
int x,z,Moon[105][105][55],Highest[105][105],n,m,Superficie,AnsDfs[105],AnsBfs[105];
bool MoonNuclear[105][105][55],Nuclear[105][105],Visit[105][105][55],VisitAns[105];
int Direction[26][3]={{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},
{1,0,0},{-1,0,0},{1,1,0},{1,0,1},{0,1,1},{-1,1,0},{1,-1,0},
{1,0,-1},{-1,0,1},{0,1,-1},{0,-1,1},{-1,-1,0},{-1,0,-1},
{0,-1,-1},{1,1,1},{-1,1,1},{1,-1,1},{1,1,-1},{-1,-1,1},
{-1,1,-1},{1,-1,-1},{-1,-1,-1}};
int SpaceManhattan(int,int,int,int,int,int);
void MarkHazard(int,int,int,int);
void FloodDfs(int,int,int,int);
void WdqerkDfs(int);
void WdqerkBfs();

int main()
{
    ios::sync_with_stdio(false);
    memset(Nuclear,true,sizeof Nuclear);
    memset(MoonNuclear,true,sizeof MoonNuclear);
    cin>>x>>z;
    for(int i=1;i<=z;i++)
        for(int j=1;j<=x;j++)
            for(int k=1;k<=x;k++)
            {
                cin>>Moon[j][k][i];
                if(Moon[j][k][i]!=0)
                    Highest[j][k]=max(Highest[j][k],z);
                if(Moon[j][k][i]==-1)
                    Nuclear[j][k]=false;
            }
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>Cannot[i].MineralType>>Cannot[i].DangerousDistances;
    cin>>m;
    for(int i=1;i<=m;i++)
        cin>>Danger[i].DangerousMineral;
    for(int i=1;i<=z;i++)
        for(int j=1;j<=x;j++)
            for(int k=1;k<=x;k++)
                for(int t=1;t<=n;t++)
                {
                    if(Moon[j][k][i]==Cannot[t].MineralType)
                    {
                        Cannot[t].MineralCoordinate[++Cannot[t].SumCoordinate].Abscissa=j;
                        Cannot[t].MineralCoordinate[Cannot[t].SumCoordinate].Ordinate=k;
                        Cannot[t].MineralCoordinate[Cannot[t].SumCoordinate].Vertical=i;
                        break;
                    }
                }
    for(int t=1;t<=n;t++)
        for(int Subscript=1;Subscript<=Cannot[t].SumCoordinate;Subscript++)
        {
            MarkHazard(Cannot[t].MineralCoordinate[Subscript].Vertical,
                       Cannot[t].MineralCoordinate[Subscript].Abscissa,
                       Cannot[t].MineralCoordinate[Subscript].Ordinate,
                       Cannot[t].DangerousDistances);
        }
    for(int i=1;i<=z;i++)
        for(int j=1;j<=x;j++)
            for(int k=1;k<=x;k++)
                for(int t=1;t<=m;t++)
                {
                    if(Moon[j][k][i]==Danger[t].DangerousMineral)
                    {
                        Superficie=1;Visit[j][k][i]=true;
                        FloodDfs(i,j,k,Moon[j][k][i]);
                        Danger[t].MineralGroup[++Danger[t].SumMineral]=Superficie;
                        break;
                    }
                }
    for(int t=1;t<=m;t++)
        sort(Danger[t].MineralGroup+1,Danger[t].MineralGroup+1+Danger[t].SumMineral);
    for(int i=1;i<=x;i++)
        for(int j=1;j<=x;j++)
            Nuclear[i][j]=Nuclear[i][j]&MoonNuclear[i][j][Highest[i][j]];
    VisitAns[1]=true;WdqerkDfs(1);
    WdqerkBfs();
    for(int t=1;t<=m;t++)
    {
        cout<<Danger[t].SumMineral<<' ';
        for(int i=1;i<=Danger[t].SumMineral;i++)
            cout<<Danger[t].MineralGroup[i]<<' ';
        cout<<endl;
    }
    return 0;
}
int SpaceManhattan(int x1,int y1,int z1,int x2,int y2,int z2)
{
    return abs(x1-x2)+abs(y1-y2)+abs(z1-z2);
}
void MarkHazard(int dx,int dy,int dz,int Distances)
{
    for(int i=1;i<=z;i++)
        for(int j=1;j<=x;j++)
            for(int k=1;k<=x;k++)
                if(SpaceManhattan(i,j,k,dx,dy,dz)<=Distances)
                    MoonNuclear[j][k][i]=false;
}
void FloodDfs(int X,int Y,int Z,int Flood)
{
    for(int i=0;i<26;i++)
    {
        int nX=X+Direction[i][0];
        int nY=Y+Direction[i][1];
        int nZ=Z+Direction[i][2];
        if(nX<0||nX>z||nY<0||nY>x||nZ<0||nZ>x||Visit[nY][nZ][nX]==true||Moon[nY][nZ][nX]!=Flood)
            continue;
        Superficie++;Visit[nY][nZ][nX]=true;
        FloodDfs(nX,nY,nZ,Flood);
    }
}
void WdqerkDfs(int Node)
{
    cout<<Node<<' ';
    for(int i=1;i<=x;i++)
    {
        if(Nuclear[Node][i]==true&&!VisitAns[i])
        {
            VisitAns[i]=true;
            WdqerkDfs(i);
        }
    }
}
void WdqerkBfs()
{
    cout<<endl<<1<<' ';
    memset(VisitAns,false,sizeof VisitAns);
    VisitAns[1]=true;
    queue<int>Queue;
    int NodeSum=1;
    Queue.push(1);
    while(!Queue.empty())
    {
        int Node=Queue.front();
        for(int i=1;i<=x;i++)
        {
            if(VisitAns[i]||Nuclear[Node][i]==0)
                continue;
            cout<<i<<' ';
            VisitAns[i]=true;
            Queue.push(i);
            NodeSum++;
            if(NodeSum==x)
                return;
        }
        Queue.pop();
    }
}

信息

ID
1063
难度
2212238
分类
(无)
标签
递交数
0
已通过
0
通过率
?
被复制
1
上传者