DFS
思路:
枚举所有起点,记录当前走过的步数和走过格子数值组成的数,用set()去重。
代码
n, m, k = map(int, input().split())
g = []
for _ in range(n):
tmp = list(map(int, input().split()))
g.append(tmp)
dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
path = set()
def dfs(x, y, u, num):
if u > k:
path.add(num)
else:
for d in dirs:
a = x + d[0]
b = y + d[1]
if a >= 0 and a < n and b >= 0 and b < m:
dfs(a, b, u + 1, num * 10 + g[a][b])
for i in range(n):
for j in range(m):
dfs(i, j, 1, g[i][j])
print(len(path))
BFS
思路:
枚举所有起点,用双端队列记录初始位置和初始位置对应的数字,记录每一步到达的位置和所走路径对应的数值,走完k步计算所有路径对应的数值并去重。
代码
from collections import deque
n, m, k = map(int, input().split())
g = []
for _ in range(n):
tmp = list(map(int, input().split()))
g.append(tmp)
dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
path = set()
def bfs(q):
nodes = []
while q:
u, v, s = q.popleft()
for d in dirs:
dx = u + d[0]
dy = v + d[1]
if 0 <= dx < n and 0 <= dy < m:
t = s * 10 + g[dx][dy]
nodes.append([dx, dy, t])
q.extend(nodes)
return q
for i in range(n):
for j in range(m):
q = deque([[i, j, g[i][j]]])
for _ in range(k):
q = bfs(q)
for node in q:
path.add(node[2])
print(len(path))