UVA-1572

解题思路:

之前看到的骚操作,主要思想就是把两个面合在一起看成两个点相连,最后只要找到一个环就可以无限克隆这个环使得无限延迟.

把符号变成数字如A-变为0,A+变为1,则0^1=1 ,这两个符号可以通过^来快速转换。

实现代码:

#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
using namespace std;
int cg(string s){
if(s=="") return -;
int ans = s[] - 'A';
return ans*+(s[]=='+');
}
int g[][];
int main()
{
int n,i,j,k,a[];
string s1;
while(scanf("%d",&n)!=EOF){
memset(g,,sizeof(g));
for(i=;i<n;i++){
cin>>s1;
for(j=;j<;j++) //取得四个面的符号
a[j] = cg(s1.substr(j*,));
for(j=;j<;j++) //g[x][y] 代表从x到y是否通路 = 1代表连通
for(k=;k<;k++)
if(a[k]!=-&&a[j]!=-&&j!=k) //剪枝
g[a[j]][a[k]^] = ; //y^1代表能与x连通的点,因为x与y在一个方块上,想让另一个方块与之相连,另一个
//方块必须存在y^1这个面,这样路线就由x到了y^1。
}
bool flag = ;
for(i=;i<;i++)
for(j=;j<;j++)
for(k=;k<;k++)
g[i][j]|=g[i][k]&&g[k][j]; //合并路径,如 1-2和2-3 可以合为1-3.
for(i=;i<;i++)
flag|=g[i][i]; //路径合并完毕后查看是否存在环,如果有环,则可以无限延伸
if(flag==) cout<<"bounded"<<endl;
else cout<<"unbounded"<<endl;
}
return ;
}
上一篇:RBAC


下一篇:利用linux信号机制调试段错误(Segment fault)