深度优先遍历
import sys
# 设置递归深度
sys.setrecursionlimit(5000)
m, n, k = map(int,input().split())
# 全局变量
ans = 0 #记录题解
visited = set() #记录已访问过的位置,避免重复统计
coordinations = [(1,0),(-1,0),(0,1),(0,-1)] # 上下左右偏移量
# digitalSums数组的索引是原始数,值是原始数对应的数位和
digitalSums = [0] * (max(m,n))
for i in range(len(digitalSums)):
num = i
while num > 0:
digitalSums[i] += num % 10
num //= 10
def dfs(x,y):
# 如果对应位置越界,则不能进入
if x < 0 or x >= m or y < 0 or y >= n:
return
# 如果对应位置的横坐标,纵坐标的数位之和超过了k,则不能进入
if digitalSums[x] + digitalSums[y] > k:
return
pos = x * n + y
if pos in visited:
return
visited.add(pos)
global ans
ans += 1
for i in range(4):
xhat = x + coordinations[i][0]
yhat = y + coordinations[i][1]
dfs(xhat,yhat)
dfs(0,0)
print(ans)
广度优先遍历
import sys
# 设置递归深度
sys.setrecursionlimit(5000)
m, n, k = map(int,input().split())
# 全局变量
ans = 0 #记录题解
visited = set() #记录已访问过的位置,避免重复统计
coordinations = [(1,0),(-1,0),(0,1),(0,-1)] # 上下左右偏移量
# digitalSums数组的索引是原始数,值是原始数对应的数位和
digitalSums = [0] * (max(m,n))
for i in range(len(digitalSums)):
num = i
while num > 0:
digitalSums[i] += num % 10
num //= 10
# 广度优先遍历
def bfs():
queue = [0]
ans = 1
visited.add(0)
while len(queue) > 0:
pos = queue.pop(0)
x = pos // n
y = pos % n
for offsetX, offsetY in coordinations:
xhat = x + offsetX
yhat = y + offsetY
# 如果对应位置越界,则不能进入
if xhat < 0 or xhat >= m or yhat < 0 or yhat >= n:
continue
# 如果对应位置的横坐标,纵坐标的数位之和超过了k,则不能进入
if digitalSums[xhat] + digitalSums[yhat] > k:
continue
# 新位置已访问过,则不能再访问
newPos = xhat * n + yhat
if newPos in visited:
continue
# 否则可以进入
ans += 1
visited.add(newPos)
queue.append(newPos)
return ans
# 算法入口
if m == 0 or n == 0:
print("0")
else:
print(bfs())