记忆化错误
  • 板块P1605 迷宫
  • 楼主Jasenn
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/11/10 18:05
  • 上次更新2024/11/10 20:35:09
查看原帖
记忆化错误
1520148
Jasenn楼主2024/11/10 18:05

n,m,t = map(int,input().split())

sx,sy,fx,fy = map(int,input().split())

visited = [[0 for i in range(m+1)]for i in range(n+1)]
#防止从该节点往下的路径再次回到该节点及其上位节点

graph = [[0 for i in range(m+1)]for i in range(n+1)]

hasresult = [[0 for i in range(m+1)]for i in range(n+1)]

for i in range(t):

	x,y = map(int,input().split())
	hasresult[x][y] = 1

hasresult[fx][fy] = 1

graph[fx][fy] = 1

def dfs(x,y):

	if x < 1 or x > n or y< 1 or y > m or visited[x][y]:
    		return 0
	if hasresult[x][y]:
    		return graph[x][y]

	visited[x][y] = 1
	graph[x][y] = dfs(x-1,y)+ dfs(x+1,y) + dfs(x,y-1) + dfs(x,y+1)
	visited[x][y] = 0
	hasresult[x][y] = 1
	return graph[x][y]

print(dfs(sx,sy))

大佬求助,

hasresult和graph用于记忆化搜索,visited用于排除走过的路,两者结合就有错?(单独只排除走过的路就可以

2024/11/10 18:05
加载中...