题目:
给出几种正方形, 每种正方形有无穷多个. 在连接的时候正方形可以旋转, 翻转.
正方形的每条边上都有一个大写英文字母加'+'或'-',00, 当字母相同符号不同时, 这两条边可以相连接, 00 不能和任何边相连.
判断给出的正方形如果能无限连接下去就输出 unbounded, 不能就输出 bounded.
思路:
这个题读完之后, 一点思路都没有, 看完紫书上的分析知道是用拓扑排序来判断有向环, 但具体的构造还是不会......
1. 将每个正方形看作一条边, 在正方形每两条边上的字母 (不包括 00) 之间连一条有向边构成一个有向图.
2. 使用(2*n)^1 = (2*n+1),(2*n+1)^1 = (2*n).
3. 利用拓扑排序来判断有没有有向环, 有则输出 unbounded, 没有就输出 bounded.
- #include <bits/stdc++.h>
- #define inf 0x3f3f3f3f
- #define MAX 1e9+7;
- #define FRE() freopen("in.txt","r",stdin)
- #define FRO() freopen("out.txt","w",stdout)
- using namespace std;
- typedef long long ll;
- const int maxn = 60;
- int n,mp[maxn][maxn],vis[maxn];
- int getId(char a,char b) {
- return (a-'A')*2+(b=='+' ? 1 : 0);
- }
- void solve(char x1,char x2, char y1,char y2) {
- if(x1=='0' || y1=='0') {
- return;
- }
- int x = getId(x1, x2)^1;
- int y = getId(y1,y2);
- mp[x][y] = 1;
- }
- void insertG(char* str) {// 建图
- for(int i = 0; i<8; i+=2) {
- for(int j = 0; j<8; j+=2) {
- if(i!=j) {
- solve(str[i],str[i+1],str[j],str[j+1]);
- }
- }
- }
- }
- bool dfs(int x) {
- vis[x] = 1;// 正在被访问中
- for(int i = 0; i<52; i++) {
- if(mp[x][i]) {
- if(vis[i])// 如果已经被访问过, 就是有环
- { return true; }
- if(!vis[i] && dfs(i))// 后续的递归中出现有环的情况
- {return true;}
- }
- }
- vis[x] = 0;
- return false;
- }
- bool topuSort() {// 拓扑排序
- memset(vis,0,sizeof(vis));
- for(int i = 0; i<52; i++) {// 个人理解因为可能有多个连通分量, 所以每一个点都要跑一把
- if(!vis[i] && dfs(i)) { // 有环
- return true;
- }
- }
- return false;// 没有环
- }
- int main() {
- while(scanf("%d",&n)!=EOF) {
- char str[9];
- memset(mp,0,sizeof(mp));
- for(int i=0; i<n; i++) {
- scanf("%s",str);
- insertG(str);
- }
- if(topuSort()) {
- printf("unbounded\n");
- } else {
- printf("bounded\n");
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2927450.html