蓝桥杯-迷宫
没有白走的路，每一步都算数🎈🎈🎈
题目描述：
已知一个30行50列的方格，方格由0和1组成，1 表示障碍物，0表示可行的方块。人从最上边开始行走，逃出这个迷宫，走到最右下角的位置。每次可以行走的方向有上下左右四个位置。向下向上向左向右分别记作DULR，并且从最上边的位置到最下边的位置有很多方法，要求记录L,D,U,R，若有多种方法，要求输出所有记录当中长度最小且字典序最小的方法。
输入描述：
输入一个30x50的数据
输出描述：
数出最佳的方案
样例输入输出：
样例输入:
010000
000100
001001
110000
样例输出：
DRRURRDDDR
算法分析：
错误代码，在得到最后一个结果的时候，即到if条件之后，没有弹栈，就直接返回去。
一些感想：
从今天下午2点到下午5点钟，就一直在写这一道题目，本来想着一小时刷个10到算法题目的。
- DFS在写迷宫求解最佳路径的时候，耗时较长，比BFS长。
- DFS适用于求解行数列数都不太大的情况，此题中30x50就算行数列数较大的情况。超时了
此代码仍旧存在一些不足：当递归到最后一个点的时候，没有弹栈。
没有处理l出现空的情况
错误代码：
- 没有弹栈，没有考虑deque以及l出现空的情况。
- 没有对结果进行排序
import os
import sys
from collections import deque
d = [[1,0],[0,-1],[0,1],[-1,0]]
n = 4
m = 6
mp = [list(map(int,input()))for i in range(n)]
flag = [[0 for j in range(m)]for i in range(n)]
q = deque()
l = []
res = []
def dfs(i,j):
if i == n-1 and j == m-1:
print(i,j)
s = ''
for k in range(len(l)):
s+=l[k]
## print(s)
res.append(s)
return
for x in range(4):
ni = i+d[x][0]
nj = j+d[x][1]
if 0<=ni<n and 0<=nj<m and flag[ni][nj]==0:
if mp[ni][nj] == 0:
q.append((ni,nj))
flag[ni][nj] = 1
## print(q) DLRU
if x == 0:
l.append('D')
elif x==1:
l.append('L')
elif x==2:
l.append('R')
elif x==3:
l.append('U')
## print("1",q)
dfs(ni,nj)
print('---------')
## print("2",q)
l.pop()
## print("3",q)
x,y =q.pop()
print(x,y)
flag[x][y]=0
flag[0][0] = 1
dfs(0,0)
print(res)
##print(l)
##print(q)样例通过代码：
此代码只是通过了样例，本题目的dfs会严重计算不出来，打算学习使用BFS来学习。
import os
import sys
from collections import deque
d = [[1,0],[0,-1],[0,1],[-1,0]]
n = 30
m = 50
mp = [list(map(int,input()))for i in range(n)]
flag = [[0 for j in range(m)]for i in range(n)]
q = deque()
l = []
res = []
def dfs(i,j):
if i == n-1 and j == m-1:
a,b = q.pop()
flag[a][b]=0
## print(i,j)
s = ''
for k in range(len(l)):
s+=l[k]
## print(s)
res.append(s)
if l !=[]:
l.pop()
return
return
for x in range(4):
ni = i+d[x][0]
nj = j+d[x][1]
if 0<=ni<n and 0<=nj<m and flag[ni][nj]==0:
if mp[ni][nj] == 0:
q.append((ni,nj))
flag[ni][nj] = 1
## print(q) DLRU
if x == 0:
l.append('D')
elif x==1:
l.append('L')
elif x==2:
l.append('R')
elif x==3:
l.append('U')
## print("1",q)
dfs(ni,nj)
## print('---------')
## print("2",q)
if l != []:
l.pop()
## print("3",q)
if len(q) != 0:
x,y =q.pop()
## print(x,y)
flag[x][y]=0
flag[0][0] = 1
dfs(0,0)
print(res)
for i in range(len(res)):
for j in range(i,len(res)):
tmp = ''
if len(res[i])>=len(res[j]):
tmp = res[j]
res[j] = res[i]
res[i] = tmp
print(res)
def ord1(s):
ans = 0
c = 1
for i in range(len(s)-1,-1,-1):
ans += ord(s[i])*c
c*=10
return ans
for i in range(len(res)):
for j in range(i,len(res)):
tmp = ''
if ord1(res[i])>=ord1(res[j]):
tmp = res[j]
res[j] = res[i]
res[i] = tmp
print(res)每日一句
好像时间一长，我们便会担心坚持的意义，会怀疑自己的努力。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2023-02-03，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录