POJ 3278 Catch That Cow

题意

给出你一条直线,和你在直线上的位置以及牛在直线上的位置,你每一次操作可以左移一个单位,或者右移一个单位,或者把你当前的坐标直接乘2作为你的新坐标。你要求出你最少要经过多少次操作才能正好移动到牛的位置上。

思路

不典型的最短路问题数据较小时可以使用BFS解决,不过本题不能盲目DFS,要注意排除掉已经不可能产生优解/更优解的情况,在这里我剔除掉的情况是:

  • 当前走的步数已经大于等于当前最优解了
  • 当前的位置已经小于0了
  • 当前的位置与牛的距离已经超过了开始时与牛的距离(合理的最坏情况下的距离)。
  • 当超过了牛的位置时,只能选择回退,如果接下来的回退所消耗的时间加上现在已经消耗的时间已经不可能再产生更优解

上述这种在搜索途中将一些预计不能产生优解/更优解的情况排除掉的方法也称为“剪枝”,这是暴力搜索中很常用、很重要的一种优化手段。

代码

 

 

POJ 3126 Prime Path

题意

给出你两个四位素数,保证这个素数不会有前导0(也就是1003起跳)。给定一个操作,在只改变一位的前提下,把当前素数变为另一个四位素数(无前导0)。现在问你至少进行多少次这样的操作才能把一个素数变为另一个。

思路

素数的朴素判断需要O(sqrt(n))的时间复杂度,显然不符合本题要求。不妨使用欧氏筛法,在O(n)的时间复杂度内预处理出10000以内的全部素数,之后O(1)时间解决查询某个数是否为素数的问题。

解决完素数问题,剩下的就是近似于求最短路的BFS过程了。具体的实作方法可以参考下面的代码。

代码

 

POJ 3087 Shuffle'm Up

题意

你需要模拟一个洗牌过程,每一次把左右两个牌堆交叉叠放在一起,然后把整个叠放好的大牌堆再分成上下两半作为左右牌堆。现在给出你初始的左右牌堆,和一个要达到的目标大牌堆,问你至少要经过多少次洗牌,才能使左右牌堆直接叠放在一起等于大牌堆。

思路

这个题的数据还是比较小的,不妨尝试模拟洗牌过程,然后设定一个洗牌次数上界,只要在上界规定之内的次数没有洗出符合要求的牌堆,就视为无解。

代码

 

POJ 3083 Children of the Candy Corn

题意

对于一个入口和出口都在边界的迷宫,有两种一定能保证走出迷宫的方案,想象你自己站在迷宫的入口,你可以一直让左手扶着墙,贴着墙走,这样最后一定会走到终点。你也可以一直让右手扶着墙,贴着墙走,最终也一定会到达终点。现在要你模拟这两种策略,分别输出这样走要经历的步数,同时再算出不限于上述策略的走出迷宫的最短路方案。

思路

对于最短路,只要使用常规的BFS就可以解决。难点在于如何模拟左手扶墙和右手扶墙。如果是以左手扶墙来遍历迷宫的话,其实是相当于每一次都先尝试去走当前面朝方向的左边,若无法走,尝试直行,还不行的话,再尝试右行和上行。每一次行走,你要想想自己身处迷宫之中,并且根据你的行走动作来改变自己的朝向,模拟这个过程就是本题的难点。

有一种比较聪明的实现方式,就是把原来的行进向量(dir),也当成朝向向量来用,往左行走相当于朝向向量左转,直行相当于无旋转,右行相当于向右旋转,下行相当于两次右旋。每一次前进时把旋转完的朝向向量当行进向量用就可以了,下一次还是按照上面所述的循环操作。

本题还有一个技巧,你只需要实现扶一边墙行走,因为从起点扶一边墙走到终点相当于从终点扶另一边墙走到起点,所以你在第一次行走完之后,只要交换起点终点的’S’和’E’,然后再执行一次从”原终点”到”原起点”的行走,就可以了。

代码

 

Editorial for 2015 ACM Course Practice Contest 1

The topic of this contest is Brute Force Searching techniques including Depth-First-Searching and Breadth-First-Searching.

The problems are ALL selected by Guo Yu (Union Class) from PKU Online Judge.The dataset and problem description are altered and translated by him.

I assessed the difficulty of these problems,implemented the solutions and wrote this editorial.Should you have any question,  please feel free to leave a comment on this post.Thanks!

If you want to practice these problems after the match, please visit ACMコース1〜DFSとBFS.

For test datasets, altered problem descriptions, and standard implementation provided by original contest holder,please check this archive ACM Course 1 .

A 迷宫还是三维的好

Problem Description

hahaschool误入了一个三维迷宫,他需要尽快离开迷宫,回宿舍打osu.他只可以上下左右移动,不能跨过障碍物,请你帮他算出他走出迷宫所需的最短距离.

输入包含多组,每组数据第一行包含三个整数数H,L,W (均不超过30)分别表示迷宫的高,长,宽.
接下来依次输入0,到H – 1层的俯视图.每层俯视图包括L行,每行W个字符.
最后一组输入为0 0 0,不需处理.
图例:
S:起点(有且仅有一个)
E:终点(有且仅有一个)
#:障碍物
. : 路
每组数据输出一个整数表示最少的步数,如果不能到达终点,请输出一行osu!以表遗憾

Original Problem

POJ 2251

Difficulty

BASIC

Key Point

Breadth-First-Searching

Tutorial

Click the following link to read:

POJ 2251 Dungeon Master

B 门前大桥下,游过一群鸭

Problem Description

“门前大桥下,游过一群鸭,快来快来数一数,二四六七八”你唱出来了对不对~
由于这首歌流传较广,一唱起来便觉得这时间再无鸭可数,也便没了兴致.
于是你开始数江,河,湖,海,水塘,浴缸,下水道……总之一切能数的水体,都要数个遍!
给出水域分布图,需要你数共有多少个两两不相连的水域.其中一个或多个相连的水体被认为是一个水域.(当且仅当格子间有一条公共边,才认为两格子相连)

输入
输入包含多组数据
第一行N,M(均不超过100)表示地图的尺寸(N*M)
接下来N行表示地图
图例:
. :陆地
W :水体

输出
输出一个非负整数,表示水域的个数

Original Problem

POJ 2386

Difficulty

BASIC

Key Point

Depth-First-Searching

Tutorial

Click the following link to read:

POJ 2386 Lake Counting

C 不扶不行

Problem Description

众所周知,yinz是一位德高望重的老爷爷.但是由于上了年纪,走路只能扶墙.为了锻炼身体,他来到了一个迷宫,机智的yinz看着迷宫的地图,开始思考扶着哪面墙走能最快到达终点,请你帮助他.yinz只可能向前后左右四个方向移动.

第一行输入一个整数 T(T<10)表示数据组数.
接下来T组数据,每组数据第一行包含两个整数数L,W (3 <= L, W <= 40)分别表示迷宫的长,宽.接下来L行,输入迷宫的地图.
图例:
S:起点(有且仅有一个)
E:终点(有且仅有一个)
#:障碍物
. : 路

每组数据输出一个整数表示最少的步数,为了表示对老年人的尊重,数据保证能够到达终点.

Original

POJ 3083

Difficulty

ADVANCED

Key Point

Breadth-First-Searching,Manipulating Directional Vectors

Tutorial

Click the following link to read:

POJ 3083 Children of the Candy Corn

D 卡牌大师

Problem Description

欢迎来到召唤师峡谷,作为一名成熟的召唤师,你拥有许多各色各样的英雄.他们是卡牌大师,卡牌大师,卡牌大师….还有卡牌大师.现在,你要做的不是中单,而是洗牌.
你洗牌的手法很娴熟,左手右手一个慢动作,一看就是新东方出来的.新东方洗牌的动作是这样的,
开始有两堆数量相等的卡牌S1,S2你需要轮流用两堆的卡牌插入,如下图所示

洗牌
当然这仅仅是第一轮,如果对牌序还是不满意,你会将这堆牌上下等分(上面的部分为S1余下的为S2)重复上面的操作,直到满意为止.
你突然好奇,要多少次轮才能得到你满意的牌序.

输入
第一行输入一个正整数N (1 ≤ N ≤ 1000),表示有N组数据
每组数据第一行输入一个正整数C(1 ≤ C ≤ 100),表示S1堆的牌数(S2的与S1相等).接下来的两行,输入两行字符串,分别表示S1和S2,其中不同的字符表示不同的牌.最后输入目标牌序.

输出
每组数据输出两个正整数,分别表示对应第几组数据,第一次获得目标牌序的洗牌次数(如果不能获得则输出-1)

Original Problem

POJ 3087

Difficulty

BASIC

Key Point

Simulation,Brute Force

Tutorial

Click the following link to read:

POJ 3087 Shuffle’m Up

E 素数们

Problem Description

素数们人口比较稀疏,要知道除了2和3相邻外,其他的素数可没那么好运气.他们每次互相拜访都会花费大量的时间来寻找.但是现在好了,素数们有特殊的”快捷通道”.比如1033要去拜访8179,他可以每次只改动某一位数,到达其他素数,最终到达8179只需要6步(1033->1733->3733->3739->3779->8779->8179).现在这种”快捷通道”已经推广了,有很多素数迫不及待的准备拜访他的朋友,请你帮助他们算出使用”快捷通道”最少需要多少步才能见到他们的朋友

输入:第一行一个正整数T表示输入数据组数(不超过100组)
每组数据包含两个四位素数a,b (不存在0002,0017,0107等输入)
输出:
对于每组数据输出最少步数.

Tips:
素数判断可以用埃式筛法预处理O(n),之后O(1)查询.

Original Problem

POJ 3126

Difficulty

BASIC(Assuming you can implement the sieve of Eratosthenes)

Key Point

Sieve of Eratosthenes,Breadth-First-Searching

Tutorial

Click the following link to read:

POJ 3126 Prime Path

F 寻宝

Problem Description

你是一名勇士,名叫ZhuRenGong.今天收到消息,沉寂多年的宝物DaBaojian又重现江湖,为了避免一场腥风血雨,时间紧迫,必须尽快赶到,夺取DaBaojian.
你有三种移动方式,假设你所在的位置为x,你可以走到x-1,x+1,或者瞬移到2*x.那么,拯救苍生的任务就交给你了,勇士.

输入
多组数据,处理到文件结束.
每组数据包括两个正整数N(0 ≤ N ≤ 100,000),K(0 ≤ K ≤ 100,000)

输出
请输出最少的步数

Original Problem

POJ 3278

Difficulty

ADVANCED

Key Point

Breadth-First-Searching with some optimisation techniques

Tutorial

Click the following link to read:

POJ 3278 Catch That Cow

POJ 2386 Lake Counting / HDU 1241 Oil Deposits

题意

在一片空地上,出现了若干水洼,对于一个有水的格子,他的八连通格子(上下左右左上左下右上右下)都可以看成和他连通形成一个大水洼。现在给你空地上水的配布,你要数出有多少个水洼。

思路

典型的“水洼问题”,利用DFS解决连通性问题是十分方便的。本题只要能够正确实现DFS就可以通过了,实现DFS的要点主要是正确地使用标记和正确的递归写法。对于DFS的实作原理不太理解的话请先思考树的先序遍历,可以参考我写的这篇文章

代码

 

POJ 2251 Dungeon Master

题意

给出一个三维迷宫,上下左右前后六联通的走法,给你起点和终点,要你求从起点到终点的最少步数。

思路

拿到问题,首先发现是在一个迷宫里面进行,联通方向有六个,求最短路,且数据规模较小,这些都是适用于BFS解题的特征。接下来的关键就是正确地实现BFS了,对BFS的实作原理不太理解的话,不妨先思考在一棵树上遍历时的BFS的实作过程。在BFS的实现过程中,需要正确地判断某个点是不是有效,需要在正确的时机打访问标记,需要正确地操作队列,注意这三点一般不会产生问题。本题并不需要我们实现图结构,因为迷宫本身就已经可以看成图了。在BFS过程中,因为搜索完当前深度的全部状态,才会取出更大深度的状态,所以在BFS过程中,只要我们进入了表示走到终点的状态,就无需再考虑其他状态了,因为即使其他状态也能表示到达终点,其深度(步数)也一定不会比第一个到达的状态少,这样可以节省一些时间。还有一些诸如“连通向量”等小技巧,可以减轻编码负担。

代码

 

初步认识图和暴力搜索

[toc]
图(Graph)作为一种非常常见且有效的模型和抽象手段,不仅是在竞赛中,乃至整个CS的学习和应用过程中都有着举足轻重的地位,尽早掌握一些关于图的概念也能辅助我们更好地分析手边的问题。本文介绍一些关于图的最基本概念和实际应用上的一些基本技术。

图的基本知识

在这里我给出这样一个问题:你站在1上,1能走到3,1能走到2也能从2走回来,7能走到5也能从5走回来,7能走到6也能从6走回来,2和5和6互相连通,1自己能走到自己,3能走到4.那么你都能走到那些点呢?

你可能很自然的会想到把我上面说的那一坨给画成一个“路线图”或“地图”,这样只要一看这个图就可以一目了然了,而接下来要说的计算机/数学中的“图”就是这样的一种抽象方式。

来和“图”桑见一面

图的定义很简单,给你几个圆,再把圆和圆之间拿线连起来,就可以称为图了。

定义: 由若干个不同的顶点与连接其中某些顶点的边组成的图形称为图。

g01
An Example of Graph

上面这个就是一个典型的图了,这个图反映的就是我上文中说的那些关系,图里绿色的圆,称为“节点/顶点(Node/Vertex)“,为了接下来叙述的方便,我给每一个节点都挂上了一个编号,在实际应用中,节点上能够挂载任何你需要的信息。圆与圆之间连接着的线,不管长成什么样,都称为“边(Edge)”,边上面也可以挂载信息。

我们发现了,上图中边中,有的是拿直线段表示的,这种边称为“无向边”,比如上面图中的2号点和5号点的连边,这样的边表示“一端(2号点)和另外一端(5号点)可以经由此边互相到达”。‘

而3号点和4号点之间的连边上面有一个箭头,方向是3号到4号,这样的边称为“有向边”,含义是“你只能从一端(3号)经由此边到达另一端(4号),但是并不能反过来”。这样看来,其实无向边可以看成两条方向互反的有向边,这一条性质非常有用。

有的时候,在两个节点之间,可能有着多条无向边或者是相同方向的有向边,这种情况,称为“重边”。

然后再看1号点,我们发现他自己居然和自己连了一条边,这样的边称为“自环”。

而看一下2号、5号、6号和7号,我们发现这四个节点,和他们之间的边共同组成了一个“环”,如果我们以一个方向沿着环行走,恐怕是一辈子也出不去了-_-#。组成环的边可以是无向的,也可以是有向的,沿着一系列的有向边行走,最后走回到了起点,这些有向边就组成了“有向环”。

给图挂载信息

我们先假设这样一种问题情境:你自驾去了一个旅游区,现在正在景区门口盘算着旅游的路线,你知道景区里面没办法加油,所以你已经加满油了,你的油箱容量是K个单位,现在给了你景区的平面图,上面记载了两个景点之间连接着的最近道路的距离(已经被折算成了通过一次要消耗的油量)和你来景区之前调查好的每一个景点的美丽程度。你需要设计一种路线,使得可以用有限的K个单位的燃料,游玩的景点的美丽程度之和最大(你不用考虑游玩结束没油怎么回景区的问题,因为你的保险公司提供免费的拖车服务)。

这个问题就是图论派上用场的时候了,我在这里随便举了一组实例:

g02

 

景区大门和每一个景点,都可以抽象为图上的一个顶点,而每一条道路都可以抽象为图上的一条边。

我们知道每一个景点都有一个“美丽程度”,这个美丽程度就体现在上面这个图里面每一个节点里填着的数字,我们把这种称为“点权”。

每一条道路,都有一个“耗油量”,体现在图上就是边上的数字就是“边权”。

所谓“权(Weight)”,其实就是一种定量的评价标准,怎么样理解附挂在图上的权,是我们自己决定的。

而图上附挂的信息又不仅仅是权值,理论上我们可以给图的任何部分挂载任何我们想要的信息,试想一下,如果我们给每一个节点挂载一个列表,上边记载了从这个可以到达的全部节点的编号,会怎么样?如果我们给每一条边挂载一个数对,上面记载了边的两端所连接的节点的序号,会怎么样?

而接下来要讲的“图的存储”,其实就是几种“挂载信息”的方式。

图的常见存储方式

计算机是不长眼睛的,你也不可能指望它看到上面我们画出来的圆和线就能解决问题。因此我们要把手中的图通过一种计算机可以理解的方式进行转化并存储才行。

常见的存储方式有四种:“邻接矩阵”、“邻接表”、“前向星”、“链式前向星”。他们各有各的特点,其中“前向星”和“链式前向星”其实是邻接表的实现方式,这两种里面我们只需要学习“链式前向星”就可以了。

邻接矩阵

首先,为了方便起见,我们要把图中每一个节点都编号,在这里我们编号1~n。接下来创建一个n*n的全是0的矩阵(或者其他你设定的用来表示无法联通的值),然后我们挨个处理图中的每一条边,对于一条有向边,从a号点指向b号点,那么我们就把矩阵的a行b列修改为1,表示从a到b可以通过。对于一条无向边,连通着a号点和b号点,那么我们就把矩阵的a行b列、b行a列都修改为1,因为无向边可以看成两条方向互反的有向边。

如果你想给边挂边权,怎么办?很简单,矩阵的数值就可以当成边权来用,不过如果你的权值和矩阵中你设定的标记冲突,你就要单独开一个数组来记录了。

如果你想给点挂点权,也需要单独开一个数组来记录。

邻接矩阵的特点是查询一个点到另外一个点之间是否有边和这条边的信息,O(1)就可以查到。但是如果我们要询问一个点连出/连入的所有边(也就是所谓的“遍历”),就必须要检查邻接矩阵的一整行/一整列,这样复杂度就是O(n)。同时,因为是使用数组保存,如果图里有重边,你最终只能保存最后保存的那一条边,也就是会丢失信息,因此一旦有无法忽略的重边,就一定不可以使用邻接矩阵。

看到这里你可能觉得邻接矩阵有点傻,那你可就错了。求多源最短路的Floyd-Warshall算法,求传递闭包的Floyd-Warshall算法,有限状态自动机的状态转移方法数等等都是要使用邻接矩阵的。

邻接表(STL vector实现)

还记得上文的“如果我们给每一个节点挂载一个列表,上边记载了从这个可以到达的全部节点的编号,会怎么样”吗?其实这就是邻接表的一种实现方式。

我们依然要给每一个节点编号,不过这时更多的是为了方便了(如果不编号,就可能要借助指针)。对于每一个点,我们给它挂上一个vector,在这里我给他起名叫to。然后我们还是挨个处理原图中的每一条边。对于一条从a到b的有向边,我们只要对a中的to.push_back(b)就可以了。对于无向边,因为无向边可以看成两条方向互反的有向边,所以就是a.to.push_back(b)和b.to.push_back(a)两步。

在这里我用了个结构体,这是为了方便我们挂载信息的。如果我们想挂点权,直接在Node里面多来一个int什么的就好,如果想挂边权,就再来一个vector,与to同步push_back对应边的权值。

邻接表非常常用,首先他是以点为主体,边是作为点的信息存在的,这一点很符合我们的思考规律。其次因为边采用vector保存,所以不用担心重边丢失的问题。邻接表逊色于邻接矩阵的地方恐怕就只有查询两个点之间是否有边了,在邻接表里面你必须遍历整个当前点上的to才能判断是不是能和另外一个点相连。但相对的,如果图中的点连接的边不多的话(这时候的图可以称为“疏松图”,反之,“稠密图”),邻接矩阵下的O(n)的遍历在邻接表下就快多了。

链式前向星(静态建表的邻接表实现)

上文中我们还提到了“如果我们给每一条边挂载一个数对,上面记载了边的两端所连接的节点的序号,会怎么样?”,其实链式前向星就是这种思路。

在这里假定你已经很明白链表的工作方式了,链式前向星其实就是图上所有边按照某种特殊的方式组成的链表。因为比较难理解,我先上代码。

使用上,还是先编号,然后挨个边处理,直接调用addEdge()方法就可以,查询一个节点所连出的边是,使用上面代码里iteration()里的方法,利用一个略微奇怪的for循环就可以办到。

我们不妨直接从代码的实现来分析链式前向星的工作原理,结构体里面的head是每一个节点在容器(数组)中所对应的第一条边的位置,next是每一条边在容器中所对应的同一起点的下一条边的位置,to则是真正的存储某一条边是指向哪一点的。

再看加边操作,注意到方法里的q是静态变量,这一点非常重要,q的作用是指示当前存储边的容器的末端(注意“末端”指的是并不是最后一个元素,而是其后的空地)的位置,相当于STL迭代器的end(),每一次加边的时候,要在to的末端写入新加边的信息,然后通过head[_from]提取出起点最近加的一条边的位置,然后我们要把新加的边的next指向那一条边,最后修改head,使得最近添加的边变更为新边,同时末端向后移动以供下一次添加之用。

理解了这样的加边方法,查询一个点连出的边的方法也就很好理解,要查询一个点的连出边,我们要先查head,知道这个点最近添加的那条边在哪里(查询结果在这里是j),然后比这条边早一些添加的就是next[j],再早一点的就是next[next[j]],更早一点的是next[next[next[j]]],再早一点的是……,就这样我们一直往时间添加时间更早的边查,直到查到空节点(用来标记链表结束)。

可以发现,链式前向星相对于邻接表的vector实现,常数更小。同时如果想直接遍历每一条边,而不考虑顺序,可以直接遍历to数组(当然,为了知道每条边的起点,你可能还需要建一个from数组),这就使得我们可以从边入手解决问题。因为是邻接表,我们也可以以点为中心来考虑问题。基本可以说链式前向星在各方面都优于邻接表的vector实现。

如果你不用数组,而是用指针来实现,那就是“前向星”了。

暴力搜索

在讲搜索之前,我们还要再来一点关于图的话题,那就是“树”,当然不是种出来的树,而是一种特别一点的图,不过就像你在大街上看到的各种树一样,能被称为一棵“树”的图一定要满足以下几种特征:

  • 每两个点之间有且仅有一条路径
  • 没有环,而且只要再添加一条边,就一定会出现环
  • 只要去掉一条边,就无法保证第一条性质
  • 只要增加一个点,为了保证第一条性质就必须还要增加一条边
An Example of Tree
An Example of Tree

如果只有光秃秃的一个节点,其实也可以称为树,树上的边的方向性也没有要求,可以有向也可以无向,当有多棵“树”同时存在的时候,这些互相没有相交的树共同组成的图也被称作“森林”。

g04
An Example of Forest

自然界的树都是有根的,同样的,有时候为了分析问题的便利,我们也会选取树上的某个节点作为“根节点”。选取了根节点的树这时候也称为“有根树”。

选取了根之后,伴随之而来的还有节点与节点之间的“辈分关系”,我们把根视为辈分最大的祖先,他连接的所有点都是它的“孩子”,而对于他连接着的所有点来说他就是这些点的“父亲”。这样的关系对于所有的节点都是一样的,我们注意到了,在一棵树上,每个节点可以有好多孩子,但是只能有一个父亲,而对于没有孩子的节点,我们对他还有一个称呼叫“叶子节点”,对于有同一个父亲的若干个节点,他们互称“兄弟节点”。

Relation on a Tree
Relation on a Tree

细心的你也发现了,上面这幅图从上面到下面颜色是越来越深的,没错,我想借此来表达有根树的“深度”概念。对于根部,他的“辈分”最大,但是他的“深度”是最小的,父亲的深度始终是比孩子节点的深度大1的。

理解了上面的这些概念,我们就可以开始说“暴力搜索”了。

我们说的“搜索”是什么

我们对搜索的认识,恐怕都是来源于“百度”、“谷歌”,也就是“从所有的信息中找出我们需要的信息的这一过程”,而我们现在接下来要说的“搜索”虽然感觉上还是和你键入几个关键字然后敲回车有一定区别的,但是实质上其实是一样的,不过现在这个过程要交给你亲自去实现。

试想这么几个问题,给你一个表示各个景点之间连通关系的图,现在让你找13号点在哪里,你如何“系统地”完成这个寻找过程?给你一个迷宫,里面有好多墙壁,现在要你找出脱出迷宫的最短路线,你又该如何“系统地”完成这一过程?更直接地,给你一棵树,制定一个根部,你能“系统地”把这棵树的亲子关系和深度都算出来吗?

这些问题,对于你来说可能就是瞟一眼那样简单,不过你知道计算机可是没有眼睛的,也没法扫视全局,因此“系统性”的算法就显得非常重要,也就是说你要有一种“套路”,而不是随便去瞟一眼这么简单。

接下来我们要介绍两种最为常见的搜索“套路”,深度优先搜索和广度优先搜索。在学习这些之前,我已经假定你理解了我上面所讲的的概念,以及递归(调用栈)队列的知识。

深度优先搜索(Depth First Search)

理解深度优先搜索(DFS)的最佳途径就是从“树的先序遍历(DLR)”开始,所谓“遍历”就是把树的每一个节点都走一遍。树的先序遍历,是指对于给定的一棵有根树,从这棵树的根部开始,不断尝试进入儿子节点(下潜),直到进入了叶子节点,然后才会返回到上一层,继续查找下一个儿子节点进入,通过不断重复这一过程,直到所有的节点都被进入并最终返回根部。简单的说就是:不断尝试探底,不走重复的路。下面举个例子来解说:

在这里我给出了一棵树,并且设定好了根部,同时因为我们的起点在根部,我把根部标记为1.

g06
Example Tree to Show DLR

根节点(1号节点),连接了两个儿子节点,按照上文所述的思想,我们优先访问最左面的那个,我们把它标记为2,并进入这个节点。

g07

 

进入2号节点之后,我们顺着刚才的思路,不断下潜,最后我们到达了叶子节点4号。

g08

 

现在我们发现没有可以用的孩子节点了,那么我们就要回到当前节点的父亲那里去,也就是3号节点。在3号节点,我们发现了除了已访问的4号节点之外的另外一个儿子,我们把它标记为5号节点,并进入。

g10

我们在5号节点又遇到了4号一样的情况,没有儿子,那样的话我们就要返回父亲节点3号。当我们返回3号,我们发现儿子已经走了个遍了,这个时候我们又要返回父亲节点2号,在2号同样没有可以没走过的儿子了,我们返回到2号的父亲节点1号。

g11

等我们回到了一号节点,我们又可以找到新的没有走过的儿子了,于是我们按照刚才的调子,进入这个儿子,这个节点已经是我们走过的第6个新节点了,给他标号6,然后我们又找到了他的儿子,进入,标号7。

g12

7号节点又是叶子节点,于是我们返回到他的父亲6号,然后发现还有一个没走过的儿子,于是进入,标号8。

g13

8是叶子节点,返回6,6没有没走过的儿子,返回1,1没有没走过的儿子。好了,任务完成了!

g14

以上就是“树的先序遍历”,是不是很简单?而DFS其实就可以理解成先序遍历在各种其他情境的推广,比如各种“图的遍历”、迷宫搜索(可以转化为图)、找出联通块(水洼问题)等等。通过思考我们也发现了,DFS实现起来的最佳方式就是递归,递归可以完美的还原我们的“下潜(发动递归)”和“返回(函数返回)”动作。下面我给出使用DFS遍历图的实现,使用了vector邻接表,所有访问到的节点,均会在标记数组vis中被标true。

如果你还是一头雾水,不妨试着将上面我做演示的那棵树建立成图,然后手动模拟一边这份实现的执行过程,就能理解了(前提是你必须知道递归的原理)。

一旦你发动了dfs(a),那么在搜索执行完毕之后,所有与a号节点直接或间接连通的点都会被在vis中标记,所以只要对这份实现稍加改动,我们就可以解决“水洼问题”了。而要想解决“迷宫出路”这种问题,我们还要稍微动下脑筋,思考一下vis这个标记数组应该怎样活用,怎样利用vis让dfs达到我们想要的效果(在这份实现中,一旦一条路被走过,就无法再次走过,而在迷宫中,我们很有可能要走之前走过的道路,这样我们就要适时地复原vis标记)。

广度优先搜索(Breadth First Search)

相对于DFS,广度优先搜索(BFS)也许更加直观一点,我们还是从“树的遍历”说起。对于一棵给定的有根树,我们依然从根开始入手,不过这次我们建立了一个队列,队列存储的是“状态”,最开始队列是空的,要开始搜索,我们要给他加入“当前在根节点”这一状态,之后我们不断拉取队伍的队首,然后分别把我们进入了各个儿子的状态逐一加入队列,直到队列清空,这个时候我们一定把每一个“在XX节点”的状态都经历过了,所以我们是走遍了整棵树。

我在这里依然用在DFS里的那棵树来举例子,图下面的方括号,表示队列的变化,左半方括号表示队列头,右半方括号表示队列尾。

最开始,我们的队列里只有1号状态,我们给它拿出来,然后发现他有两个儿子,于是分别创建进入2号儿子的2号状态和进入3号儿子的3号状态,并将他们加入队列尾端。

g15
[1] -> [2,3]
接下来,我们取出队列头的2号状态,我们发现它只有一个儿子,我给他标号4,于是把“进入4号节点”的4号状态加入队列。

[2,3] -> [3,4]
[2,3] -> [3,4]
接下来,取出队列头的3号状态,我们发现它有两个儿子,在这里标号为5和6,于是借此生成5号和6号状态,加入队列。

[3,4] -> [4,5,6]
[3,4] -> [4,5,6]
之后,取出队列头的四号状态,发现在这个状态所在的4号节点有两个儿子,在这里标号7和8,同时据此创建状态并加入队列。

[][]
[4,5,6] -> [5,6,7,8]
最终,队列弹出的5,6,7,8号状态均是在叶子节点的状态,无法创建新状态,队列就此清空,我们完成了遍历任务!来看一下我们整个BFS的全貌吧:

State tree of the whole BFS process
State tree of the whole BFS process

相信你已经可以基本理解BFS的工作方式了。

显然光会个遍历树是不够的,将上面所讲述的思考方式拓展一下,BFS也可以完成“图的遍历”,“迷宫最短路”等问题,下面我会给出一种用于遍历图的BFS实现,图的存储方式采用vector实现的邻接表。

 

选择适合的搜索方式

一招鲜显然并不能吃遍天,DFS,BFS中的任何一个都不能应付全部的场合。DFS使用递归实现,因此当搜索深度比较大的时候就存在巨大的栈溢出风险,而实用模拟栈实现的DFS又十分复杂,得不偿失,因此当栈空间不足以支持DFS时,必须换用BFS。BFS相对于DFS,实现相对比较繁琐,如果使用STL queue的话,会带来一些常数上的劣势(这种劣势在SPOJ等黑心OJ上十分明显),模拟队列又可能会占用大量内存。因此我们需要根据问题的实际来考虑使用哪种搜索方式。

一般来说,DFS在求连通性问题上具有十分的优势(Tarjan SCC/DCC算法均基于DFS),而BFS在求最短路问题上占上风(Dijkstra/SPFA算法均基于BFS),掌握好这两种算法是学好图论的基础。如果你够细心的话,你会发现我们在DFS的同时给树进行了编号,那个编号其实叫做“DFI(DFS序)”,这个东西有着一些神奇的应用。同时DFS和BFS又可以升级为一种考虑问题的思想,当然这些高级一些的问题就需要我们在练习的时候慢慢体会了。

 

本文系hahaschool原创,同时作为Tic ACM Club讲稿,未经许可禁转载。

 

BZOJ 2780 / SPOJ JZPGYZ Sevenk Love Oimaster

题意

给出一系列的字符串,我们把这些串叫母串,然后给你若干字符串,对于每一个字符串,你要求出在多少个母串中可以找到和给出的字符串相同的母串的字串。

思路

子串问题,要借助后缀系列解决,这个题使用了后缀自动机。但是通常意义的后缀自动机都是针对一个母串建立的,现在我们手里有一堆母串,这时候就需要我们进行活用,来创建“广义后缀自动机”,这个自动机将可以接受母串集合里所有的字串。

广义后缀自动机的建立方法其实是在一般的自动机创建基础之上,增加了一些东西。构造后缀自动机的方法是增量法,构造广义后缀自动机的方法也是一样的,但是我们从第个二串开始,一位一位增量的时候,我们有可能会用到构造到一半的自动机的某些节点或者某些转移边。对于当前将要加入的mxn(最长可接受字串长度)值,和当前追加节点时的last,如果last有一条转移边可以用,而且即将加入的新节点的mxn值正好等于last的mxn+1,这说明既存的节点和我们将要加入的节点是等价的,这一轮的追加到这里就可以结束了。如果存在转移边,但是转移边连着的节点mxn值并不是last的mxn+1,这个时候就需要我们使用在平常构造后缀自动机中使用的“拆点”方法。复制既存的节点作为符合我们mxn要求的节点,调整parent关系和所有自动机上父亲节点的转移关系,就像我们在平常构造自动机时为了防止mxn异常缩短采用的“拆点”方法一样。如果last节点不存在可用的转移边,这时候按照普通的增量法处理就可以。(如果觉得费解,不妨直接参考我的MultiSAM_Append()方法)。

创建完广义后缀自动机,这还只是个开始。接下来我们要提取出自动机中的所有的parent关系,创建parent树。我们注意到,在parent树中,一个节点的子树代表的是以这个节点为后缀的全部字串。举个例子就是,对于“banana”的”ana”代表节点(mxn值3),他的子树就代表了”ana“,”nana“,”bana“,”anana“,”banana“,这一系列字串。这一特性有什么用呢?

注意到题意,我们要找到给出的串在多少个串中匹配,如果我们按照正常的方法在广义后缀自动机上完整地匹配这个串(如果匹配有中断,那就说明这个串不存在于母串集合的字串当中),这个时候转移到的最终状态对应节点的parent树的子树,就是在母串集合中所有的以给出的串为后缀的字串。如果我们给parent树上的每一个节点挂一个列表,标记这个节点都被哪些字符串利用了,这样只要我们逐一统计子树中的每一个节点,就可以知道当前给出的串在几个母串中存在,问题就可以解决了。

但是对于每一棵子树都统计一次,复杂度很大,显然需要再优化。优化的方法就是“DFS序把树压平”然后“离线处理”。首先遍历parent树,纪录每一个节点进入时的DFN和出去时的DFN,从进去到出去这两个DFN之间的所有节点(包括出入两个节点)显然就是parent的子树了。现在我们的问题就转变为了在某个数组上一段给定的区间求有多少个不同的数字,而且还是离线处理,这种问题可以使用一种O(n)的处理方法,详情可以参考BZOJ 1878 HH的项链

问题到了这里,终于是完美地解决了。

 

代码

 

树状数组(BIT)实现

在这里只提供模板。

一维情形

提供区间和功能,支援单点delta更新。sum得到的是[1,pos]的值的和。

二维情形

提供矩阵和功能,支援单点更新,sum得到的是从(1,1)拉到(posi,posj)的矩阵中数的总和。

 

Scroll to top