记录一哈这里的内部搜索与外部搜索的区别。
这里有一个本质的区别就是搜到一个新的点的时候,从不同的点搜到这个新的点对所求的状态有没有区别。
比如说内连同,也就是连通性的问题,如果说一个点能从上面的点搜过来,或者能从下面的点搜过来,都无所谓。
因为我只需要保证这个点是联通的并且能够在这个点的基础上再进行一次深搜就行了。
外联通则不一样,如果一个点是外联通的话,从不同状态搜过来的新的状态则完全不同。比如马走日这道题中的第四个点
如果是从第一个点到,那么此时的遍历方案就是1->4,
如果说是从第一个点到第二个点再到第四个点,那么此时的遍历方案就是1->2->4,
如果说是联通性问题里面的话,两种方案没有关系,因为第二种方案枚举到4的时候4已经被标记过了,在连通性问题里面我们只需要判断每一个点的联通性就够了,既然已经判断过了就不管了。
但是在马走日的问题里面我们可以看到,两种方案所代表的状态完全不一样,第一种方案是枚举的是以14开头的所有状态,第二种方案则枚举的是以12开头的所有方案,不仅两种方案完全不一样,两种方案往后无论是遍历到哪一个点都不可能是同一种方案,因为两种方案的开头两种走法都完全不一样。
这样看来连通性问题由于只需枚举到每一个点的状态,不用关心遍历过程中出现的不同状态,所以不需要还原现场,属于一种特殊的dfs。