题目描述:
超哥来到一间密室，忽然一阵阴风把门关上了。魔法学校的门需要魔力才能打开，而超哥没有那间密室的魔力。超哥继续往密室深处走，发现一堆魔法瓶和一些古老的文字。上面写着：欲开启密室，需收集所有瓶中魔力。开启魔法瓶需严格按照顺序，否则将焚毁密室…文字记载了一个N×N的0,1矩阵GN×N，还记录了任意两个魔法瓶之间的开启规则：你可以从任意一个魔法瓶开始。魔法瓶j能在紧随魔法瓶i之后被安全打开，当且仅当Gi,j=1。魔法瓶j紧随魔法瓶i之后被打开，密室会被焚毁，当且仅当Gi,j=0。文字最后写道，任意两个魔法瓶，都可以相邻。即:Gi,j⊕Gj,i=1(∀i≠j)你能帮超哥找到一个开启所有魔法瓶方案吗？
输入:
第一行一个整数N，魔法瓶的个数，接着N行，每行N个数，0或1。第i行第j列为1，表示开启第i个魔法瓶后，下一个开启的魔法瓶可以是j。保证矩阵 第i行第j列与 第j行第i列数值不同，第i行i列为0。N≤1000
输出:
N个数，空格隔开，表示打开魔法瓶编号顺序。
样例输入:
2
0 0
1 0
样例输出:
2 1
问题分析：
该题的本质即：
在一“特殊”有向图中寻找一条不重复经过某个点的可行路径遍历图中所有点。
而这个图究竟有多特殊呢？
该图的特殊性描述如下：
1、该图中任意两点之间存在一条路径；
2、该路径为单向不可逆，即若存在A->B,则不存在B->A,反之亦然
由以上两条特殊性可推出如下结论：
若存在一条路径经过图中若干个点，例：2->1->3->4
则必存在图中任意不在该路径中的点可插入该路径中使路径连通：
假设该数组为arr，图中任意不在该路径中的点为5，则遍历arr[5][2],arr[5][1],
arr[5][3],arr[5][4],若存在arr[5][num] = 1;则插入该数前，若不存在为1的值则插入路径尾部，因为若arr[5][4] = 0;由特殊性2可知arr[4][5] = 1;即点4可到达点5。
java实现如下：
网友评论