背景
最近在准备ACM校赛，遇到一个深度优先、广度优先搜索的问题，求一个地图块中有多少连接成一片的地方
整个数据是用二维数组表示的，于是我打算利用练习这个题的机会总结一个代码模板，遇到求连接片的问题可以直接套用。
甚至遇到“生命游戏”、“兰顿蚂蚁” 等等二维数组类问题也可以直接套用，同时也打算更新这类算法
众所周知，python的numpy库是一个优秀的第三方库，但是如果是算法比赛和做算法题，就不能引用这个库了。但是可以直接来这里复制~这是代码模板
待更新- 水平、垂直反转容器方法
- 提供一个遍历操作二维容器里每个值的方法
- 添加生命游戏算法（如果是原地算法更好）
- 添加兰顿蚂蚁算法
遇到新的算法问题会继续添加
使用代码def solution(ww, hh):
width = ww
height = hh
m = Container2D(width, height)
for y in range(height):
line = input()
for x, char in enumerate(line):
if char == "*":
m.set(x, y, 0)
else:
m.set(x, y, 1)
return m.bfsGetGroupCount(1)
# 生成完毕
def main():
while True:
height, width = input().split()
height = int(height)
width = int(width)
if height == 0 and width == 0:
break
print(solution(width, height))
算法题运算结果
5 5 ****@ *@@*@ *@**@ @@@*@ @@**@ >>> 2
可以看到，算法求出来@符号连接成的区域有两块。
代码模板# -*- encoding: utf-8 -*-
"""
二维数组、二维容器代码模板 算法模板
2021年11月28日
by littlefean
"""
from collections import deque
class Container2D:
def __init__(self, w, h, initVal=0):
"""
按照宽高初始化一个二维容器
w: 宽度
h: 高度
initVal: 每一个格子上的初始值
"""
self.width = w
self.height = h
self.mapArr = []
self.initVal = initVal
for y in range(self.height):
line = []
for x in range(self.width):
line.append(initVal)
self.mapArr.append(line)
def set(self, x, y, val):
"""
甚至一个位置上的值
Time: O(1)
"""
if self.inContainer(x, y):
self.mapArr[y][x] = val
def get(self, x, y):
"""
获取一个位置上的值
Time: O(1)
"""
if self.inContainer(x, y):
return self.mapArr[y][x]
else:
raise Exception("访问越界")
def inContainer(self, x, y):
"""
某个下标位置是不是在里面，避免出现越界错误
Time: O(1)"""
return x in range(0, self.width) and y in range(0, self.height)
def show(self):
"""
打印情景
Time: O(n^2)
"""
print("==" * self.width)
for y in range(self.height):
for x in range(self.width):
val = self.get(x, y)
if self.initVal == val:
print(".", end=" ")
else:
print(val, end=" ")
print()
def bfsGetGroupCount(self, targetVal):
"""
在二维数组中广度优先搜索，有多少个目标值连接成块的块数
targetVal: 寻找的目标值
当前默认是斜着也算连接着，如果想改成上下左右算连接，
更改 getRoundFunc = roundLoc
改成 getRoundFunc = adjoinLoc
Time: >= O(n^2)
"""
def roundLoc(x, y) -> list:
"""返回一个点周围一圈8个点"""
return [(x + 1, y), (x + 1, y + 1), (x, y + 1), (x - 1, y + 1), (x - 1, y), (x - 1, y - 1), (x, y - 1),
(x + 1, y - 1),
]
def adjoinLoc(x, y) -> list:
"""返回一个点周围 上下左右四个点"""
return [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]
getRoundFunc = roundLoc # 获取点的方法
visitedSet = set()
resFinal = 0
for yIndex in range(self.height):
for xIndex in range(self.width):
# 遍历每一个格子
if self.get(xIndex, yIndex) == targetVal:
# 该格子是要寻找的值
if (xIndex, yIndex) in visitedSet:
# 这个格子已经访问过了之前
continue
else:
# 这个格子 是 新访问的
resFinal += 1
visitedSet.add((xIndex, yIndex))
# 广度优先遍历
q = deque()
q.append((xIndex, yIndex))
smallSet = {(xIndex, yIndex)} # 用来防止和自身重复
while len(q) != 0:
loc = q.popleft()
for aLoc in getRoundFunc(*loc):
# 遍历当前这个点的邻居点
if not self.inContainer(*aLoc):
# 越接
continue
if aLoc in smallSet:
# 已经问过
continue
if self.get(*aLoc[0]) == targetVal:
q.append(aLoc)
visitedSet.add(aLoc) # 添加访问过了的集合
smallSet.add(aLoc) # 添加广度优先自身不重复集合
# 广度优先结束
return resFinal
...
