打开网易新闻 查看更多视频
深度优先搜索 入门：城堡问题
将问题的各状态之间的转移关系描述 为一个图,则深度优先搜索遍历整个图的 框架为：
打开网易新闻 查看精彩图片
例题：百练2815 城堡问题 右图是一个城堡的地形图 。请你编写一个程序，计 算城堡一共有多少房间， 最大的房间有多大。城堡 被分割成 m ×n(m≤50 ， n≤50)个方块，每个方块可 以有0~4面墙。
输入输出 输入 程序从标准输入设备读入数据。 第一行是两个整数，分别是南北向、东西向的方块数。 在接下来的输入行里，每个方块用一个数字(0≤p≤50)描述。用一个数 字表示方块周围的墙，1表示西墙，2表示北墙，4表示东墙，8表示南 墙。每个方块用代表其周围墙的数字之和表示。城堡的内墙被计算两 次，方块(1,1)的南墙同时也是方块(2,1)的北墙。 输入的数据保证城堡至少有两个房间。 输出 城堡的房间数、城堡中最大房间所包括的方块数。 结果显示在标准输出设备上。
打开网易新闻 查看精彩图片
解题思路：
打开网易新闻 查看精彩图片
打开网易新闻 查看精彩图片
打开网易新闻 查看精彩图片
热门跟贴