《区域周长》
本题要求以某个格子为起点,找出一块连通区域,并且求出周长。
又是一道常见的2D地图上的搜索问题,做过hiho一下第156周《岛屿》这道题目的同学一定很熟悉。
我们把《岛屿》这题中使用的dfs稍加修改就能作为本题找出连通区域的基础算法:
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] == gird[i][j]:
dfs(_x, _y)
在此基础上我们需要思考如何计算区域的周长。对于一个区域中的方格来说,它一共有上下左右四条长度为1边。其中某条边是边界的一部分当且仅当这条边另一侧的方格不是本区域的方格或者根本不存在(在地图之外)。
所以在我们dfs的过程中,在从方格(i, j)尝试扩展到方格(_x, _y)时,可以顺便判断夹在(i, j)和(_x, _y)的之间的边是不是边界。如果是,我们就累计在变量ans中:
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 NOT inside the boarder:
ans++
else if NOT visited[_x][_y]:
if grid[_x][_y] == gird[i][j]:
dfs(_x, _y)
else:
ans++
代码不知为嘛没弄上,修改也没权限是shenmegui=_=