/////////////////////////////////////////////////////////////////////////////////////////////////////// 作者：tt2767 声明：本文遵循以下协议自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 查看本文更新与讨论请点击： 链接被删请百度： CSDN tt2767 ///////////////////////////////////////////////////////////////////////////////////////////////////////
这题值得学习的几点： 1.输入匹配的代码十分优美！ 2.把A+,A-映射成2n,2n+1做，然后通过（2n）^1 = 2n+1 , （2n+1）^1 = 2n 来反转，不得不说十分精妙！
题解：由于正方形是无限的，，把要去连接编号与被链接的正方形上的其他可扩展编号看成节点，被链接的正方形看成边，寻找次有向图的环。 题目中的例子： A- |->->->->->->->->->->A+|->->->->->->->->(A+,A+,00) 要连接的节点————两正方形连接点————被链接的正方形的其他节点
G[60][60];int vis[60];//把A+-变成2n和2n+1int ID(char x, char y);cont(char x1,char x2,char y1,char y2);bool dfs(int u);bool cyc();int main(){int n;while(scanf(“%d”,&n) == 1 && n){memset(G,’\0′,sizeof(G));memset(vis,0,sizeof(vis));for(int i = 0 ; i < n ; i++){char s[9];scanf(“%s”,s);for(int j = 0 ; j < 4 ; j++)for(int k = 0 ; k < 4 ; k++)if(j != k)//对每个边都与其他非自身的边连接cont(s[j*2],s[j*2+1],s[k*2],s[k*2+1]);}if(cyc())(“bounded”);}return 0;}int ID(char x, char y){return (x-‘A’)*2 + (y == ‘+’ ? 0 : 1);}void cont(char x1,char x2,char y1,char y2){if(x1 == ‘0’ || y1 == ‘0’)return ;int u = ID(x1,x2)^1 ;int v = ID(y1,y2);G[u][v]++;}bool dfs(int u){vis[u] = -1;for(int i = 0 ; i < 52 ; i++){if(G[u][i]){if(vis[i] < 0) return true;;}}vis[u] = 1;return false;}bool cyc(){for(int i = 0 ; i < 52 ; i++)if(!vis[i] && dfs(i))return true;return false;}
造物之前，必先造人。
