题意:

给出一些正方形,这些正方形的每一条边都有一个标号。这些标号有两种形式:1.一个大写字母+一个加减号(如:A+, B-, A-......), 2.两个0(如:00);这些正方形能够任意翻转和旋转。当两个正方形通过旋转或翻转,使得他们的公共边为同样大写字母而且符号相反时,他们就能够彼此结合拼在一起。如今给出n中正方形。每种正方形有无限多种,问这些正方形是否能拼成一个无限大的结构。

题解:

easy想到。要使这些正方形形成无限大地结构。那么这些正方形通过拼接后一定能循环(即通过不断地拼接出现了和曾经同样地正方形),那么就能够通过推断将这些正方形地全部可能地拼接方式连有向边。然后推断是否有有向环,就可以通过拓扑排序来推断。

代码:

#include <queue>
#include <vector>
#include <cstdio>
#include <string>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 52 + 10;
int G[maxn][maxn], vis[maxn]; int ID(char a, char b)
{
return (a - 'A')*2 + (b == '+' ? 0 : 1);
}
void conect(char a1, char a2, char b1, char b2)
{
if (a1 == '0' || b1 == '0')
{
return ;
}
int u = ID(a1, a2)^1, v = ID(b1, b2);
G[u][v] = 1;
}
bool dfs(int u)
{
vis[u] = -1;
for (int v = 0; v < 52; v++) if (G[u][v])
{
if (vis[v] == -1) return true;
if (!vis[v] && dfs(v)) return true;
}
vis[u] = 1;
return false;
}
bool find_cycle()
{
memset(vis, 0, sizeof(vis));
for (int i = 0; i < 52; i++) if (!vis[i])
{
if (dfs(i)) return true;
}
return false;
}
int main()
{
// freopen("/Users/apple/Desktop/in.txt", "r", stdin);
int n;
while(scanf("%d", &n) == 1 && n)
{
memset(G, 0, sizeof(G));
while (n--)
{
char s[10]; scanf("%s", s);
for (int i = 0; i < 4; i++)
{
for (int j = 0; j < 4; j++) if (i != j)
{
conect(s[i*2], s[i*2+1], s[j*2], s[j*2+1]);
}
}
}
if (find_cycle()) printf("unbounded\n");
else printf("bounded\n");
} return 0;
}

最新文章

  1. Oracle工具类-生成数据库现有Job的创建脚本
  2. 细说ASP.NET Core静态文件的缓存方式
  3. TCP与UDP协议
  4. struts2视频学习笔记 09-10(struts2处理流程,指定多个struts配置文件)
  5. SpriteKitCommonUse
  6. nginx一致性hash及应用场景。
  7. 常用的MySQL图形化管理软件
  8. stat~~~访问文件状态的利器
  9. LINK : fatal error LNK1000: Internal error during IncrBuildImage
  10. uva12486 Space Elevator(数位dp)
  11. poj3659树状DP
  12. RH253读书笔记(5)-Lab 5 Network File Sharing Services
  13. Java数据库 高级查询
  14. 2018年Web前端自学路线
  15. Java 读书笔记 (十四) Java 方法
  16. 《k8s-1.13版本源码分析》-源码调试
  17. Fiddler教程--简介
  18. 对于eclipse building workspaces 慢的问题,解决方法
  19. Python练习-8
  20. java 类变量初始化顺序

热门文章

  1. 阿里云server改动MySQL初始password---Linux学习笔记
  2. C/C++获取本地时间常见方法
  3. 基于TI Davinci架构的多核/双核开发高速扫盲(以OMAP L138为例),dm8168多核开发參考以及达芬奇系列资料user guide整理
  4. 使用 Facebook开源动画库 POP 实现真实衰减动画
  5. 关于Maven报错的一些解决办法(别处贴的)
  6. 浅析.Net数据操作机制
  7. pix格式的摸索(二)
  8. JavaScript--数据结构与算法之二叉树
  9. 微信小程序从零开始开发步骤(二)创建小程序页面
  10. [Angular] How to get Store state in ngrx Effect