算法代表着用系统的方法描述解决问题的策略机制，北京大学《算法基础》课程将带你一一探索枚举、二分、贪心、递归、深度优先搜索、广度优先搜索、动态规划等经典算法，体会他们巧妙的构思，感受他们利用计算解决问题的独特魅力。顺利完成本课程，你将不但能够掌握这些算法的原理，还能够对这些算法进行灵活应用以及准确实现。本课程的中的编程任务，将充分训练你的思维能力和动手能力，促成全面、缜密思考问题的习惯。达到本门课程的要求，即意味者你具备了初步的算法基础和较强的编程实现能力。
深搜之城堡问题
Loading...
From the course by Peking University
算法基础
281 ratings
From the lesson
深度优先搜索（1）
想象我们在一座迷宫里，如何才能找到出口呢？最直观的方法是从入口开始沿着一条路一直走到底，如果遇到分叉路口就选择其中一条道路走下去，如果遇到死胡同就退回到上一个分叉路口，选择另一条道路走下去，如果遇到出口就成功走出迷宫了。这种尽量往深处走的做法即是深度优先搜索(深搜）。深搜算法编程简单，简洁易懂，空间需求也比较低，但是这种方法的时间复杂度往往是指数级的，如果不加以优化，时间效率无法忍受。本模块将通过实例继续讨论深度优先搜索算法中优化程序的基本方法“剪枝”，即在设计剪枝判断方法的基础上，避免一些不必要的遍历过程，从而提高算法效率。
Meet the Instructors
Jiaying Liu 刘家瑛, Ph.D.Associate Professor
Institute of Computer Science & Technology
郭 炜讲师
北京大学信息科学技术学院教学所
大家好，听说这一节课郭老师要给大家讲这个深搜，又听说这是最后一节课了，所以我来蹭一下存在感。
好啊， 这回我们又两个人一块讲啊， 不过刘老师你今天怎么穿得这么漂亮啊，我没有办法集中注意力讲课啊。
我擦。郭老师这明显是混淆视听。
好，我们要讲的是乘法问题。这是一个深搜的入门题。
对，我们先说说深搜到底是怎么工作的。
就是我们在解决一些问题的时候，老会牵涉到各种各样的状态，然后各个状态之间可以互相转移，一个状态可以到达另外一个状态，
那往往我们就会把状态之间互相的可达性画成一个图，
那么我们对于深搜来讲的话，实际上就是去
遍历整个图的这么一个过程。对，有时候我们需要遍历整个图。
那怎么遍历呢？那我们首先图上面所有的点当然都是没有访问过的，对吧，
那我们在main里面可以用一个循环，在这循环里面每次找一个没有访问过的点k，
然后以这个点k作为起点，去调用dfs这个递归函数，做深度优先搜索。
对然后我们在这个DFS里头的话，首先去看这个访问的
这个点k，然后去判断一下这个点是不是
作为是不是被访问到了。如果访问到了，直接就返回了。如果
没有被访问到就要首先标记一下它是访问过了，然后这时候就去找
和这个v这个点相邻的每一个u点然后再去，再次去调用这个递归函数。所以相邻就是说从v可以
一步就走到u，那我们对这种每一个相邻的点u我们都递归的调用dfs u，从u开始再继续进行深度优先搜索。
啊，那，看看右边那个图呗。我们看这个图。
这图它可不一定是连通的。对吧，那我们在做这个图的深度优先搜索的时候
假设我们一开始选了2这个点作为起点，也就是说
一开始选的这个点k是2，那我们从2出发，就可以走到4，然后从4出发又走到了8，
然后又走到了5，然后就走不动了，这块所有点都访问过了，而且到不了别的地方，
那这第一次以2为起点的深度优先搜索就结束了。然后就把跟2相连的点全部都照出来了。
对，所以如果是广度优先搜索的话，就应该是2,4,5,8，
对，深度优先搜索它是2,4,8,5或者2,5,8,4都有可能吧，
那现在以2为起点的深度优先搜索做完了那整个图还没有
全部访问完，所以我们这个外循环呢它还是能在图中找到没有被访问的点 比如说这个1，那就会从1开始做一遍深度优先搜索。
就可以走到1,3,6,7把剩下的部分走完。
这个就是深度优先搜索的一个基本的这个过程。一般来说是用递归来实现的。
我觉递归会比较好的描述整个思路，比较直观，就按照正常的想法就是。
那如果不用递归，你用一个栈也是可以的。我们知道广度优先搜索是用队列，那深度优先搜索归根到底
是用栈来实现的，只不过你写递归函数的话， 是编译器生成的代码去帮你维护这个栈。
好，那我们接着就来看具体这个百练2815的这个城堡问题。
这个城堡问题其实就是讲说你看右边这张图，是吧，它实际上展示的就是一个
城堡的地形图。看起来错综复杂的像一个迷宫，
迷宫问题都这样。然后这个城堡里面呢，有很多小方块，
这些方块呢，能够构成一个个的房间，就是联通的方块
能够构成房间。怎么样来算连通的呢？如果两个方块之间都有墙壁阻挡就没法连通了。
比方说这个方块和这个方块之间有一堵墙， 然后没有别的路能够走到这个方块，那
这两个方块就不连通，那它们可能就分别属于不同的房间，对。
这是一个房间，然后呢这个呢，又是一个房间。
好，那我们这个问题就是，所以我们这题目呢 是希望你能够写一个程序去判断说这个城堡里头一共有多少个房间。
并且最大的房间里面是多大？最大房间包含多少个方块？
那这个题目的数据描述是这样的，
这输入一开始就告诉你，这4就代表这整个
城堡，它是有4*7这么多个方块所组成的，就是4行7列，
然后这底下就一个矩阵，每一个数字就代表
一个方块，那一个数字描述的是什么呢？比如说这个方块它所对应的是11，
11这个数字它描述的是这个方块周围到底有哪些墙，
那墙不是有4个方向就是东南西北，对吧，那如果这个数字11里面包含一个1，
那它就说明这个方块它是有西墙的， 在这。如果这个数字里面还包含一个2，
那就说明这个房间它是有北墙的。如果这数字里面还包含一个4，
那它说明这个房间是有东墙的，如果还包含一个8，就说明它有西墙，那对于
这个方块来说，我们看到它所对应的数字是11，我们可以分出来是1+2+8所以我们就知道，
它是没有东墙的，有其他的墙。等于说这个
一个数字，你把它的二进制形式写出来，也就是11，它的二进制形式写出来是多少，
是1,0，啊你从后往前数，
11,1011，
那这个就是西墙，这个是北墙，
这个是南墙，这个东墙是0，就没有，就这样。
好了，那现在，整个 每一个格子都已经通过这样的方式来定义好了
墙壁的分布，对，它周围到底有哪些墙。现在你要找出最大的
房间包含几个方块，以及一共有多少个房间。
对，所以输出就包含了两行，那这个是典型的深度优先搜索的问题。
那基本的思路就是我们可以从一个 方块出发，看看这个从一个方块出发都能走到哪些其他的方块，
一直到走不动为止，那它走过的所有方块就可以形成一个房间。
那当然我们就把从一个方块出发所到达的其他所有的方块都给它
染上颜色，对，其实就是标记一下，标记一下这是属于哪个房间的。然后一个房间走完以后，我们就另外再找一个起点。
然后这个起点它必须不属于原来已经标记出来的这个房间，对吧，另外再找一个起点的方块，
再做一遍深度优先搜索，看看又能够到达哪些连通的方块，把这些连通的方块全部组成一个房间，再给它染色，
然后我们最后一共统计一下，染了几种颜色，以及每种颜色都有多少个
方块，就比方说，我们从这个 起点出发，哎，我们从这个起点出发去进行染色，可以这样走，走走走走过来，
走走走走到这， 走不动可以回溯，回溯到这还能走到这，哎， 然后就再也走不出去了。我们每个点都没法在往其他没有标记过的点走，
所以我们就找到了一个房间，这个房间我们标记成1，它就相当于
这块。啊，那至于其他2,3呢我们就不演示了。
对，所以通过这样的方式就可以直接去统计最后的这个
房间数和每个房间的方块数。
嗯，好，那我们就可以写出这个 程序来了。这个程序一开始这个r,c是代表这个城堡的行列数。
rooms当然就是用来存放对所有方块的这个描述，
然后color是用来对方块进行染色， 一开始所有的方块颜色都是0嘛，
后面就会对程序变成1,2,3什么的，这个maxRoomArea当然就是
我们求到的这个最大房间的
方块数了，roomNum就是求得的一共有多少个房间。
roomArea是 正在探索的那一间房间它的面积，我们不断的探索这些房间它的面积就有可能
不断增大。啊，然后我们用的这个DFS来进行深度优先搜索。那我们看DFS之前我们先看MAIN是
干什么的。就把这个行列读进来，每一个房间的描述读进来，
然后把所有的房间的颜色都初始化成0，都还没有标记过，
然后我们就注意，这是 用一个两重循环遍历所有的方块，以每一个方块
作为起点，如果它颜色没有被标记过。对，如果方块i,k它还没有被
刷上颜色，就说明这个方块还没有走过。那我们就要以它为起点进行深度优先搜索。
那我们每发现一个还没有走过的方块，我们就知道它肯定属于某一个还没有被探索过的房间，
所以我们就要把这个房间的数目给它+1， 那接下来我们就要探索这个房间了，那探索这个房间的时候这房间的面积我们初始化成0，
然后我们就去做这个DFS，IK，就以i,k这个
方块作为起点，探索这个房间，探索这个房间
结束以后呢，我们就会得到了这个房间的面积roomArea，就在DFS里面算出来，
然后我们就要用一个maxRoomArea就是已经
找到的最大的房间面积去跟这个roomArea去比较， 然后有可能更改了这个maxRoomArea，最后我们就输出这个roomNum，maxRoomArea就行了。
嗯，所以重点还是要去看这个DFS IK，啊对，DFS怎么写呢，它说的意思就是
从I,K这个方块开始进行探索，去找一个房间，
然后我们看，如果I,K这个方块它已经被染上色了，
那我们就没什么好继续往下走了，对吧，我们就return,没法从一个已经被染色的点作为起点再去走了，这是没有意义的。
那ik这个点它如果还没有被染上色呢？
那我们就要从它开始往下走了。那ik没有被染上色的话，说明它属于某一个房间，
那这个房间的面积自然要加1，对吧，加1就是ik这个方格，
然后我们要把ik这个方格染上色，它颜色的记号就是roomNum，
因为我们roomNum一开始是0，到第一个房间roomNum就是1，走到第二个房间roomNum就是2，对吧，
所以现在roomNum就是在3之前的这个房间号，在main里面，
一开始是roomNum是0，在这里没找到一个房间的起点我们就给它++了，对吧，所以说roomNum就代表当前正在它所在的房间号，
我们走到一个方块我们就把这个方块的颜色标记为当前这个房间号， 然后我们就要考察什么，
从这个ik出发它还能走到
哪些个方块，要考察它周围相邻的四个方块，
那你要考察四个方块，比如说你要考察你能不能
往西边那个方块走，那就要看这个方块的西面有没有墙，
那如果西面有墙的话你就不可以走过去了。
那我们怎么判断这个ik这个方块西面有没有墙呢？ 我们就让rooms
ik去跟1进行与操作，因为 每一面墙它就对应rooms
ik的 二进制表示形式里面的那一位，西面
那个墙是对应于第0位，就是最右边的那一位，
我们跟它，让这个rooms ik跟1进行与操作，如果与出来的结果是
0的话就说明西面是没有墙，与出来结果是1的话就说明 西面是有墙的，如果西面没有墙的话，等于0的话就说明
西面没有墙，西面没有墙的话那我们就知道 我们可以走到ik
的西边也就是Ik-1了，对吧，
就是向左走一格，然后我们就以ik-1作为起点
再去作为深度搜索，再去往下探索，那同理
我们要判断它能不能往北走，那就是拿这个rooms ik去跟2去与操作，如果与出来是0就说明背面是
没有墙的，那我们就 接着往北面的那个方块作为起点进行登录优先的搜索。
所以这个问题就解决了。你有什么要说的？
这只是一个简单题，都没什么可发挥的，对啊对，那我们就来看下一题。
那其实呢，刚才讲到的这个递归函数其实也可以不用递归来实现，对吧，真的啊，我都不知道哎，
哎呀，太假了，郭老师，其实呢对吧，我们刚才说，
这个递归的这个函数实际上是对程序对里用堆栈的形式进行维护了，所以，
所以呢，我们就业可以不利用递归，
单纯自己通过去写一个栈去解决这样一个问题，对应刚才的那个
dfs函数的话呢，我们可以首先去在这个非递归的
函数当中我们首先去定义好一个room,这个room的话它是一个struct, 那么它里面的话就包含了一个行号
和列号r和c，然后会定义一个构造函数，初始化一下这个r和c，之后的话我们自己就等于利用一个栈，
来去构建后续的整个这么一个过程，所以我们写了一个stk，
首先本身这个stk是空的，
那么我们只要去调用这个dfs这个函数的时候我们首先做的事就是把room
rc这个 方块，是方块，对吧，这个方块呢把它放到这个
我们这个栈中间去，就是stk.push我们把这个room
放进去，然后之后我们就是去用这个while 循环，只要去判断说我们当前的这个栈是
不为空的，那么就我们就会去做这个，把这个
栈顶的这个元素来 赋给这个room r，看下栈顶的元素咯，
对然后这时候的话如果说本身这个方块已经是被染色的，
就跟我们刚才去判断说这个color ik是不是
已经被标记过了，如果它被染过了话那么我们
就让它，刚才那个函数就是return了，那么对于这个栈来讲的话我们自然就会让它把对应的这个栈顶的这个元素把它
pop出去，对就是递归函数它本身在自身return的时候，
也就会把栈里面栈顶元素给他pop出来，或者是编译器自动生成的代码所干的事情。
对，那么我们这边实际上就是自己去手动去把它做了一下这个去维护栈的这个工作。
之后的话，如果它本身这个块是没有被标记过颜色的话，
那么一样的，我们在iles这边首先去让它的roomArea去++，
然后此外的话，把对应的这个roomNum标记给对应的方块ik,就标记下
它的颜色，之后就进行一系列跟刚才一样的四个方向去判断一下，那么如果它对应的方向上是没有
靠墙的，比方说是
没有这个西墙的，然后，这个时候的话我们就在刚才的这个递归函数中间 我们就再次调用哪个DFS函数了。
那么在这个非递归的利用栈的形式去实现的时候我们
只需要去做压栈的这个iii，把对应的新的方格
第i行第k-1个的这个方格把它放到栈中间，
所以就stk.push一下对应的这个方格就可以了。对，递归函数进入一层，栈也会攒一层，
对，所以这样的话我们实际上就可以利用，自己写的堆栈的形式去完成刚才的这个递归函数的
这个描述。啊，刘老师你太高明啦。讲得比我的清楚多啦。好，继续下一题。
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
