迷宫 蓝桥杯 641

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

X 星球的一处迷宫游乐场建在某个小山坡上。它是由 10×1010×10 相互连通的小房间组成的。

房间的地板上写着一个很大的字母。我们假设玩家是面朝上坡的方向站立，则：

• L 表示走到左边的房间，

• R 表示走到右边的房间，

• U 表示走到上坡方向的房间，

• D 表示走到下坡方向的房间。

X 星球的居民有点懒，不愿意费力思考。他们更喜欢玩运气类的游戏。这个游戏也是如此！

开始的时候，直升机把 100100 名玩家放入一个个小房间内。玩家一定要按照地上的字母移动。

迷宫地图如下：

UDDLUULRUL

UURLLLRRRU

RRUURLDLRD

RUDDDDUUUU

URUDLLRRUU

DURLRLDLRL

ULLURLLRDU

RDLULLRDDD

UUDDUDUDLL

ULRDLUURRR

请你计算一下，最后，有多少玩家会走出迷宫，而不是在里边兜圈子？

思路：DFS搜索，先写DFS函数，之后用vis数组记录走过的元素，如果走过则将vis数组对应的该点记为‘1’，当重新走到‘1’的点时，意味着路径成死循环，无法走出迷宫。这里需要注意的是走出迷宫的判断条件（ x < 0 or x > 9 or y < 0 or y > 9）

遍历+递归

#深度dfs递归
map = ['UDDLUULRUL',
       'UURLLLRRRU',
       'RRUURLDLRD',
       'RUDDDDUUUU',
       'URUDLLRRUU',
       'DURLRLDLRL',
       'ULLURLLRDU',
       'RDLULLRDDD',
       'UUDDUDUDLL',
       'ULRDLUURRR']#这里字符串元素要用单引号括起，用双引号，后面会提示数组越界
#map 可以这样读取
#mp=[list(input()) for i in range(10)]
count = 0
vis = [[0] * 10 for i in range(10)]


def find(x, y):
    if x < 0 or x > 9 or y < 0 or y > 9:  # 走出迷宫
        global count
        count += 1
        return True

    if vis[x][y] == 1:  # 已走过
        return False

    vis[x][y] = 1  # 若之前没走过，则标记走过

    if map[x][y] == "U":
        find(x - 1, y)#递归
    elif map[x][y] == "D":
        find(x + 1, y)
    elif map[x][y] == "L":
        find(x, y - 1)
    elif map[x][y] == "R":
        find(x, y + 1)
    return False


for i in list(range(10)):
    for j in list(range(10)):
        vis = [[0] * 10 for i in range(10)]#遍历每个坐标起点开始前都先清零
        find(i, j)

print(count)

或

def dfs(x,y):
  if x<0 or y<0 or x>10 or y>10:
    return 1
  if vis[x][y]==1:
    return 0
  vis[x][y] =1
  if mp[x][y]=='L': return dfs(x,y-1)
  if mp[x][y]=='R': return dfs(x,y+1)
  if mp[x][y]=='U': return dfs(x-1,y)
  if mp[x][y]=='D': return dfs(x+1,y)


mp=[list(input()) for i in range(10)]
ans = 0
for i in range(10):
  for j in range(10):
    vis = [[0]*10 for i in range(10)]
    if dfs(i,j)==1:
      ans+=1
print(ans)