UVa 572

Oil Deposits

from Volume 2. Data Structures :: Graphs

Description

输入一张金矿的截面图，求有几个金快。要注意 “horizontally”、 “vertically”、 “diagonally” 这三个单词，说明几个金子只要竖直、水平斜角有相连就算同一块金块。

Solution

简单经典的图论问题，求无向图的连通分支数，即图的强连通分支数。 有定理：

在强连通分支算法中，选择任何顶点做起始点来执行深度优先搜索遍历，得到的强连通分支的解相同。

所以这也是经典的DFS问题。 遍历每个点，碰到金块就把它FloodFill标记成泥土，最后数到多少个金块输出就可以了。 要注意在各个HDOJ和POJ上，这道题的样例有问题，在某行尾多了一个空格。而POJ虽然据说数据比较水，但是可能用了样例做测试点，所以在读 m，n 时用 getchar( ) 过滤回车的话，就会悲剧。 而 UvaOJ 并没有这个问题，可以放心提交。