[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");
}
}

最新文章

  1. MFC 获取图像的大小
  2. python——请求服务器(http请求和https请求)
  3. ASPNET 导出EXCEL表
  4. jquery实现简单的Tab切换菜单
  5. 做一个MVC4的项目时留下的经验--增加IPrange
  6. UVa 1479 (Treap 名次树) Graph and Queries
  7. Weak Event Patterns
  8. GMT-Note 基本参数详细说明
  9. 当浏览器不支持placeholder,所执行的函数
  10. docker学习笔记5:利用commit命令创建镜像 和 删除本地镜像
  11. NSRange:NSMakeRange
  12. 安卓无法生成R文件原因
  13. iOS UICollectionView(转二)
  14. react native 中实现个别页面禁止截屏
  15. IdentityServer4之Resource Owner Password Credentials(资源拥有者密码凭据许可)
  16. NLP入门(三)词形还原(Lemmatization)
  17. python数据类型之内置方法
  18. 深度学习中 droupout层是咋回事??
  19. docker运行中的container怎么修改之前run时的env
  20. iOS UI-三种简单的动画设置

热门文章

  1. Spring整合Quartz分布式调度(山东数漫江湖)
  2. bzoj 2733 平衡树启发式合并
  3. Android控件——TextView,EditText
  4. python urllib2练习发送简单post
  5. 【Python学习笔记】多版本python使用pip安装第三方库
  6. Python2.7.3 Tkinter Entry(文本框) 说明
  7. x64dbg
  8. SQL中char、nchar、varchar、nvarchar、text概述【转】
  9. pypcap 安装
  10. js获取鼠标的位置