【图论】Self-Assembly(6-19)
2024-08-27 08:13:26
[UVA1572]Self-Assembly
算法入门经典第6章6-19(P172)
题目大意:有一些正方形,每条边上都有A-~Z- A+~Z+的编号,或者00,A+的边可以拼A-,反之亦然。00的边什么都不能拼。问是否能无限去拼。
试题分析:直接做没有头绪,但是发现可以旋转和翻转,这样就可以从任意正方形喀什了。我们将A-~Z+这52种连有向边,最后判断有没有有向环即可。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std; inline int read(){
int x=0,f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) x=x*10+c-'0';
return x*f;
}
const int MAXN=100001;
const int INF=999999;
int N,M;
int T;
char a[5],b[5];
vector<int> vec[101];
int vis[1001]; int Hash(int k){
return (a[k]-'A'+1)*2-(b[k]=='-'?1:0);
}
bool dfs(int x){
vis[x]=-1;
if(x%2==0) x--;
else x++;
for(int i=0;i<vec[x].size();i++){
int to=vec[x][i];
if(vis[to]==-1) return true;
else if(!vis[to]&&dfs(to)) return true;
}
if(x%2==0) x--;
else x++;
vis[x]=1;
return false;
} int main(){
while(scanf("%d",&N)!=EOF){
for(int i=1;i<=70;i++) vec[i].clear();
for(int i=1;i<=N;i++){
for(int j=1;j<=4;j++)
cin>>a[j]>>b[j];
for(int j=1;j<=4;j++){
if(a[j]=='0') continue;
for(int k=j+1;k<=4;k++){
if(a[k]=='0') continue;
int at=Hash(j);
int bt=Hash(k);
vec[at].push_back(bt);
vec[bt].push_back(at);
}
}
}
memset(vis,0,sizeof(vis));
bool flag=false;
for(int i=1;i<=52;i++){
if(!vis[i]&&dfs(i)) {flag=true; break;}
}
if(flag){
puts("unbounded");
}
else puts("bounded");
}
}
最新文章
- MFC 获取图像的大小
- python——请求服务器(http请求和https请求)
- ASPNET 导出EXCEL表
- jquery实现简单的Tab切换菜单
- 做一个MVC4的项目时留下的经验--增加IPrange
- UVa 1479 (Treap 名次树) Graph and Queries
- Weak Event Patterns
- GMT-Note 基本参数详细说明
- 当浏览器不支持placeholder,所执行的函数
- docker学习笔记5:利用commit命令创建镜像 和 删除本地镜像
- NSRange:NSMakeRange
- 安卓无法生成R文件原因
- iOS UICollectionView(转二)
- react native 中实现个别页面禁止截屏
- IdentityServer4之Resource Owner Password Credentials(资源拥有者密码凭据许可)
- NLP入门(三)词形还原(Lemmatization)
- python数据类型之内置方法
- 深度学习中 droupout层是咋回事??
- docker运行中的container怎么修改之前run时的env
- iOS UI-三种简单的动画设置