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;
	}
}