《岛屿》题目分析
本题是一道非常经典的2D地图上的搜索问题,类似的问题还包括走迷宫、求房间数目等。
这道题需要我们求出三个数值,一是海岛数目,二是面积不同的海岛数目,三是形状不同的海岛数目。
第一个小问题是最基本的搜索问题。
一般我们可以从上到下、从左到右扫描,直到发现一个没有处理过的'#'。然后从这个'#'开始沿着4个方向扩展,把连在一起的'#'都找出来。这些连在一起的'#'就组成一个岛屿。
伪代码如下,当然用bfs代替dfs也是没问题的:
for i = [0 .. N):
for j = [0 .. M):
if NOT visited[i][j] AND grid[i][j] == '#':
dfs(i, j)
dfs(i, j):
int dx[4] = {-1, 1, 0, 0}
int dy[4] = {0, 0, -1, 1}
visited[i][j] = true
for d = [0 .. 4):
int _x = i + dx[d]
int _y = j + dy[d]
if (_x, _y) is inside the boarder AND NOT visited[_x][_y] AND grid[_x][_y] == '#':
dfs(_x, _y)
第二个小问题很容易就可以在第一个小问题的基础上求得。我们只需在dfs/bfs找岛屿的过程中保存一下'#'的数目即可。
第三个小问题判断形状相同,我们可以用相对位置来判断。
以样例数据为例,第一行的"####"对应的坐标(行从上到下,列从左到右)依次是(0, 1)(0, 2)(0, 3)(0, 4)。如果我们以其先最上其次最左的点,也就是(0, 1)为基准的话,相对位置序列是(0, 0)(0, 1)(0, 2)(0, 3)。
同理第三行的"####"的坐标依次是(2, 0)(2, 1)(2, 2)(2, 3),其相对位置也是(0, 0)(0, 1)(0, 2)(0, 3)。两个岛屿形状相同,当且仅当它们的相对位置序列完全相同。
所以我们需要在dfs/bfs找岛屿的过程中把陆地的位置都保存下来。
值得一提的是如果我们按照确定的顺序搜索陆地,(例如以上代码中先行后列扫描第一块陆地,同时在dfs中保持按上下左右的顺序扩展陆地)那么对于两个形状相同的岛屿,我们求出的坐标序列恰好就是一一对应的。
如果我们还不放心,可以将坐标序列重新排序之后,再选择第一个坐标为基准点,求出相对位置序列。
我也是。。。