首页 > 代码库 > Poj 1022

Poj 1022

2024-09-28 16:16:02   215人阅读

传送门：http://poj.org/problem?id=1022

计算四维结合体体积，类比三维

由于不确定编号，用了一个map存储

有两种情况输出Inconsistent，1、两个单位四维体相结合的面不为相对的面，2、单位四维体没有全部连通

最后计算体积用四个方向维度的长度相乘。

这里计算维度的长度用一个深搜，每碰到一个不为0的面相应维度+1,最后维度/2+1

这个方法其实我还没太懂……

 1 #include<iostream>
 2 #include<cstring>
 3 #include<map>
 4 using namespace std;
 5 
 6 struct node{
 7     int side[8];
 8 };
 9 
10 bool flag;
11 int t,n;
12 int w,x,y,z;
13 int m;
14 int begin;
15 int maxx;
16 int marked[10000];
18 map<int,node> cube;
19 map<int,node>::iterator it;
20 
21 void dfs(int i){
22     if(marked[i]){
23         return;
24     }
25     if(m==n){
26         return;
27     }
28     marked[i]=1;
29     m++;
30     for(int k=0;k<8;k++){
31         if(cube[i].side[k]){
32             if(k==0||k==1)w++;
33             else if(k==2||k==3)x++;
34             else if(k==4||k==5)y++;
35             else if(k==6||k==7)z++;
36             dfs(cube[i].side[k]);
37         }
38     }
39     return;
40 }
41 
42 int main(){
43     cin>>t;
44     while(t--){
45         cin>>n;
46         cube.clear();
47         for(int i=0;i<n;i++){
48             int num;
49             cin>>num;
50             for(int j=0;j<8;j++){
51                 cin>>cube[num].side[j];
52             }
53         }
54         flag=true;
55         for(it=cube.begin();it!=cube.end();it++){
56             for(int j=0;j<8;j++){
57                 if(it->second.side[j]){
58                     if(j%2&&cube[it->second.side[j]].side[j-1]!=it->first){
59                         flag=false;
60                         break;
61                     }
62                     else if(j%2==0&&cube[it->second.side[j]].side[j+1]!=it->first){
63                         flag=false;
64                         break;
65                     }
66                 }
67             }
68             if(!flag){
69                 cout<<"Inconsistent"<<endl;
70                 break;
71             }
72         }
73         if(!flag){
74             continue;
75         }
76         memset(marked,0,sizeof(marked));
77         m=0;
78         it=cube.begin();
79         begin=it->first;
80         w=0;x=0;y=0;z=0;
81         dfs(begin); 
82         if(m!=n){
83             flag=false;
84             cout<<"Inconsistent"<<endl;
85             continue;
86         }
87         if(flag){
88             cout<<(w/2+1)*(x/2+1)*(y/2+1)*(z/2+1)<<endl;
89         }
90     }
91 }

 

Poj 1022


联系
我们