Отримання знань

дистанційна підтримка освіти школярів


Упаковка 4D кубов
http://acm.pku.edu.cn/JudgeOnline/problem?id=1022

   Входные данные

   Выходные данные

   Пример входных данных

   Пример выходных данных

   Анализ условия и обсуждение идеи решения

   Пример решения на С++:

#include < iostream >
#include < map >
#include < queue >
#define MAXINT 2000000000
#define MININT -2000000000
using namespace std;
struct block {
int i, x, y, z, w;
bool v;
int a[9];
block() { i=x=y=z=w=0; v=false; }
block(int _i) { i=_i; x=y=z=w=0; v=false; }
};
int ox[9]={0,-1,1,0,0,0,0,0,0};/*x offsets*/
int oy[9]={0,0,0,-1,1,0,0,0,0};
int oz[9]={0,0,0,0,0,-1,1,0,0};
int ow[9]={0,0,0,0,0,0,0,-1,1};

bool bfs(map<int, block> *blocks, int *amin, int *amax) {
queue<block*> q;
q.push(&(blocks->begin()->second));/*start block (let be origin)*/
for (map<int, block>::iterator it=blocks->begin();it!=blocks->end();it++)
it->second.v=false;
while (!q.empty()) {
block *b=q.front();
q.pop();
if (b->v)
continue;
b->v=true;
for (int j=1;j<9;j++) {
int index=b->a[j];
if (!index)
continue;
block *bl=&((*blocks)[index]);
bl->x=b->x+ox[j];
bl->y=b->y+oy[j];
bl->z=b->z+oz[j];
bl->w=b->w+ow[j];
if (bl->x<amin[0]) amin[0]=bl->x;
if (bl->y<amin[1]) amin[1]=bl->y;
if (bl->z<amin[2]) amin[2]=bl->z;
if (bl->w<amin[3]) amin[3]=bl->w;
if (bl->x>amax[0]) amax[0]=bl->x;
if (bl->y>amax[1]) amax[1]=bl->y;
if (bl->z>amax[2]) amax[2]=bl->z;
if (bl->w>amax[3]) amax[3]=bl->w;
q.push(bl);
}
}
for (map<int, block>::iterator it=blocks->begin();it!=blocks->end();it++)
if (!it->second.v)
return false;
return true;
}
int main(void) {
int cases;
cin>>cases;
while (cases-->0) {
int n;
cin>>n;
map<int, block> blocks;
int ids[n];
for (int i=0;i<n;i++) {
cin>>ids[i];
block b=block(ids[i]);
b.a[0]=ids[i];
for (int j=1;j<9;j++)
cin>>b.a[j];
blocks[ids[i]]=b;
}
/* check for inconsistency */
bool good=true;
for (int i=0;good&&i<n;i++) {
block b=blocks[ids[i]];
for (int j=1;good&&j<9;j+=2)
good&=(!b.a[j]||blocks[b.a[j]].a[j+1]==ids[i]);
}
if (!good) {
cout<<"Inconsistent\n";
continue;
}
int amin[4]={MAXINT,MAXINT,MAXINT,MAXINT},
amax[4]={MININT,MININT,MININT,MININT};

good=bfs(&blocks, amin, amax);
if (!good) {
cout<<"Inconsistent\n";
continue;
}
cout<<(amax[3]-amin[3]+1)*(amax[2]-amin[2]+1)*(amax[1]-amin[1]+1)*(amax[0]-amin[0]+1)<<endl;
}
}

 

Попередня Зміст Наступна
В системі: гості - (1); користувачі - (0)