M12558: 岛屿周长
matrices, dfs, http://cs101.openjudge.cn/pctbook/M12558
用一个n * m的二维数组表示地图，1表示陆地，0代表海水，每一格都表示一个1*1的区域。地图中的格子只能横向或者纵向连接（不能对角连接），连接在一起的陆地称作岛屿，同时整个地图都被海水围绕。假设给出的地图中只会有一个岛屿，并且岛屿中不会有湖（即不会有水被陆地包围的情况出现）。请判断所给定的二维地图中岛屿的周长。
输入
第一行为n和m，表示地图的大小(1<=n<=100, 1<=m<=100)。接下来n行，每行有m个数，分别描述每一格的数值。数值之间均用空格隔开。
输出
只有一行，即岛屿的周长（正整数）。
样例输入
3 4
1 1 1 0
0 1 0 0
1 1 0 0样例输出
14来源：cs10116 final exam
解题思路：注意到正方形周长为 4，并且每个方向与其他正方形相连则少条边，直接加保护圈，写公式，遍历一遍，直接完成。
思路：某个陆地格子对周长的贡献值是 4-周围的陆地数，其余的就是普通二维数组、加保护圈。
python
n,m = map(int,input().split())
l = [[0]*(m+2)] +[[0] +list(map(int,input().split()))+[0] for _ in range(n)]+[[0]*(m+2)]
ans = 0
for i in range(1,n+1):
for j in range(1, m + 1):
if l[i][j] == 1:
ans += 4-l[i+1][j]-l[i][j+1]-l[i-1][j]-l[i][j-1]
print(ans)思路：用总长度减去接触消失的长度即可，块数乘4-接触边乘2即可。
python
# 王沛然，24物理学院
n,m=map(int,input().split())
k=0
sl=[]
for _ in range(n):
sl.append(list(map(int,input().split())))
for i in range(n):
for j in range(m):
if sl[i][j]==1:
k+=4
if i<n-1 and sl[i+1][j]==1:
k-=2
if j<m-1 and sl[i][j+1]==1:
k-=2
print(k)dfs思路:
给矩阵加上保护圈，预存四个方向，遍历矩阵上为1的点，处理过的点设为-1跳过，该点周边(遍历四个方向)的点(判断在矩阵范围内)为0时，周长加一，为1时递推
python
n, m = map(int, input().split())
# 初始化地图，外层加了一圈0
the_map = [[0] * (m + 2) for _ in range(n + 2)]
for i in range(1, n + 1):
the_map[i][1:-1] = list(map(int, input().split()))
directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]
count = 0
def dfs(x, y):
global count
the_map[x][y] = -1 # 标记为已访问
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < n + 2 and 0 <= ny < m + 2:
if the_map[nx][ny] == 0:
count += 1
elif the_map[nx][ny] == 1:
dfs(nx, ny)
# 遍历地图，从每个1开始进行DFS
for i in range(1, n + 1):
for j in range(1, m + 1):
if the_map[i][j] == 1:
dfs(i, j)
print(count)解题思路：画一画就能发现，上下左右只要有0就周长+1。记得加保护圈0。
python
n, m = map(int, input().split())
A = []
A.append([0 for i in range(m+2)])
for i in range(n):
A.append([0] + [int(x) for x in input().split()] + [0])
A.append([0 for i in range(m+2)])
ans = 0
for i in range(1, n+1):
for j in range(1, m+1):
if A[i][j] == 1:
if A[i-1][j]==0:
ans += 1
if A[i+1][j]==0:
ans += 1
if A[i][j-1]==0:
ans += 1
if A[i][j+1]==0:
ans += 1
print(ans)python
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
n, m = map(int, input().split())
a = [[0]*(m+2)]+[[0]+[int(x) for x in input().split()]+[0] for _ in
range(n)]+[[0]*(m+2)]
c = 0
for i in range(1, n+1):
for j in range(1, m+1):
if a[i][j] == 1:
for k in range(4):
if a[i+dx[k]][j+dy[k]] == 0:
c += 1
print(c)dfs
python
#gpt
def dfs(grid, i, j):
if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] == 0:
return 1
if grid[i][j] == -1:
return 0
grid[i][j] = -1 # 标记已经访问过的陆地
perimeter = 0
perimeter += dfs(grid, i + 1, j)
perimeter += dfs(grid, i - 1, j)
perimeter += dfs(grid, i, j + 1)
perimeter += dfs(grid, i, j - 1)
return perimeter
def islandPerimeter(grid):
perimeter = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
perimeter = dfs(grid, i, j)
break
return perimeter
# 读取输入
n, m = map(int, input().split())
grid = []
for _ in range(n):
row = list(map(int, input().split()))
grid.append(row)
# 调用函数计算岛屿周长并输出结果
print(islandPerimeter(grid))bfs,
python
from collections import deque
directions = [[1,0],[0,1],[-1,0],[0,-1]]
n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
discovered = [[False]*m for _ in range(n)]
def edge(x,y):
count = 0
for dx, dy in directions:
if x+dx < 0 or y+dy < 0 or x+dx >= n or y+dy >= m:
count += 1
else:
if grid[x+dx][y+dy] == 0:
count += 1
return count
def discover(x,y):
perimeter = edge(x,y)
land = deque()
land.append((x,y))
discovered[x][y] = True
while land:
x, y = land.popleft()
for dx, dy in directions:
nx, ny = x+dx, y+dy
if 0<=nx<n and 0<=ny<m and not discovered[nx][ny] and grid[nx][ny] == 1:
land.append((nx,ny))
discovered[nx][ny] = True
perimeter += edge(nx,ny)
return perimeter
for i in range(n):
for j in range(m):
if grid[i][j] == 1:
print(discover(i,j))
exit()