Self-Assembly (UVa 1572)

　　原题地址：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=9

　　这题做了挺久，参考了网上一些大神们的代码，有几个点要搞懂。

　　首先，将题目转化成图论模型。以正方形为边，标号为点，构造有向图。具体构造方法：

 　　　　　　

　　对于正方形中的任意一个标号 X，若为 X+ ，则存在 X- 可以到达这个正方形，及 X- 可以到达这个正方形除 X+ 外的任意一点。这样，题目就转化成了一个有向图，而根据题意，要构成无限大的图，只要有向图中存在环路即可，因此可以用拓扑排序做。

　　还有一个很巧妙的技巧，2*n ^ 1 = 2*n + 1, (2*n + 1) ^ 1 = 2*n, 可以实现 X+ 与 X- 之间的转化。

　　AC代码：

/*    Self-Assembly (UVa 1572) */
#include <iostream>
#include <cstring>
using namespace std;

const int maxn = 52;

int a[maxn][maxn];        //存放有向图
int vis[maxn];    //标记遍历 
char s[10];                //读取每一个数据 

void connect(char x1, char x2, char y1, char y2);        //连接两个点 
int getID(char c1, char c2);                            //获得一个点的编号 
bool solve();                                            //检查是否存在环 
bool dfs(int u);                                        //找环 

int main(){
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int n;
    while(cin >> n){
        getchar();
        memset(a, 0, sizeof(a));
        memset(vis, 0, sizeof(vis));
        
        while(n--){
            scanf("%s", s);
            //以正方形为边，标号看成点，建立有向图
            for(int i=0; i<4; i++)            //与正方形其中一个标号 a 可以连接的标号 b， 连接除 a 以外的其他标号 
                for(int j=0; j<4; j++)
                    if(i != j)
                        connect(s[2*i], s[2*i+1], s[2*j], s[2*j+1]);
        }
        
        if(solve())
            cout << "unbounded" << endl;
        else
            cout << "bounded" << endl;
    }
} 

void connect(char x1, char x2, char y1, char y2){
    if(x1 == '0' || y1 == '0')        // 00 不可以和任何标号连接 
        return    ;
    int num1 = getID(x1, x2) ^ 1;    //与 x 这个点相连的标号的编号。  
    int num2 = getID(y1, y2);
    a[num1][num2] = 1;
}

int getID(char c1, char c2){
    return (c1 - 'A')*2 + (c2 == '+' ? 1 : 0);
}

bool solve(){
    for(int i=0; i<maxn; i++){
        if(dfs(i))
            return true;
    }
    return false;
}

bool dfs(int u){
    vis[u] = -1;        //进入栈 
    
    for(int v=0; v<maxn; v++){
        if(a[u][v] == 1){
            if(vis[v] == -1)
                return true;
            else if(vis[v] == 0) {
                if(dfs(v))
                    return true;
            }
        }
    }
    
    vis[u] = 1;        //出栈 
    return false;
}