迷宫

admin 管理员组

文章数量: 887021

迷宫

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

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

• LL 表示走到左边的房间，
• RR 表示走到右边的房间，
• UU 表示走到上坡方向的房间，
• DD 表示走到下坡方向的房间。

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

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

迷宫地图如下：

UDDLUULRUL
UURLLLRRRU
RRUURLDLRD
RUDDDDUUUU
URUDLLRRUU
DURLRLDLRL
ULLURLLRDU
RDLULLRDDD
UUDDUDUDLL
ULRDLUURRR

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

主要思路：

先用一个字符串str1保存，迷宫分布

1.先把边缘能走出迷宫的位置找出来，

        即上边缘向上走的位置

        即下边缘向下走的位置

        即左边缘向左走的位置

        即右边缘向右走的位置

这里是用flag列表统计，找到了下标为

flag = [0, 4, 5, 8, 93, 99]即为能走出的位置

2.再以此假定从0~100位置每个人开始走，

        当然如果某人起始下标和标记的flag列表中某下标一样，则可以走出去。

        当起始下标不一样，就开始行走，行走策略是（因为这里是字符串表示，且刚好100人对应100个位置（0~99下标）），故有以下规律：

        if str1[k] == 'U':
            k -= 10
        elif str1[k] == 'D':
            k += 10
        elif str1[k] == 'L':
            k -= 1
        else:#R
            k += 1

        行走后再判断一下，是否有人走过的位置与flag标志列表中的一致，有就直接算一位

        其中为了避免死循环，人一直走的情况，加一个cur列表，记录该人走过的位置下标，如果入列表路径中有与之前相重合的，则一定会死循环，这种情况说明不用找了。

str1 ="\
UDDLUULRUL\
UURLLLRRRU\
RRUURLDLRD\
RUDDDDUUUU\
URUDLLRRUU\
DURLRLDLRL\
ULLURLLRDU\
RDLULLRDDD\
UUDDUDUDLL\
ULRDLUURRR"
#标志能走出去的位置
flag = []
for i in range(10):#i表示行，第几行for j in range(10):#j表示列，第几列#处理边界上一定能走通的位置，标记一下，即只要有人走到了这个标记处就能出迷宫if i == 0 and str1[i*10+j] == 'U':flag.append(i*10+j)if i == 9 and str1[i*10+j] == 'D':flag.append(i*10+j)if j == 0 and str1[i*10+j] == 'L':flag.append(i*10+j)if j == 9 and str1[i*10+j] == 'R':flag.append(i*10+j)
# UDDLUULRUL\
# UURLLLRRRU\
# RRUURLDLRD\
# RUDDDDUUUU\
# URUDLLRRUU\
# DURLRLDLRL\
# ULLURLLRDU\
# RDLULLRDDD\
# UUDDUDUDLL\
# ULRDLUURRR"
#处理这100个人
count = 0#记录走出的人数
for i in range(0,100):k = iif k in flag:count += 1continuecur = []#记录这个人走的路径如第一个人下标为0直接上走,cur=[0],第8个人下标为7，先右走再上走,cur=[7,8]cur.append(k)#记录起始位置while True: #第一位是原k不用考虑if str1[k] == 'U':k -= 10elif str1[k] == 'D':k += 10elif str1[k] == 'L':k -= 1else:#Rk += 1if k in flag:#找到了标志的正确位置，能出去count += 1breakif k in cur:#说明有循环了，走不出去,不用走了breakcur.append(k)
print(count)

蓝桥云课结果：

本文标签： 迷宫