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