首页 > 试题广场 >

地下迷宫

[编程题]地下迷宫

热度指数：19588 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小青蛙有一天不小心落入了一个地下迷宫,小青蛙希望用自己仅剩的体力值P跳出这个地下迷宫。为了让问题简单,假设这是一个n*m的格子迷宫,迷宫每个位置为0或者1,0代表这个位置有障碍物,小青蛙达到不了这个位置;1代表小青蛙可以达到的位置。小青蛙初始在(0,0)位置,地下迷宫的出口在(0,m-1)(保证这两个位置都是1,并且保证一定有起点到终点可达的路径),小青蛙在迷宫中水平移动一个单位距离需要消耗1点体力值,向上爬一个单位距离需要消耗3个单位的体力值,向下移动不消耗体力值,当小青蛙的体力值等于0的时候还没有到达出口,小青蛙将无法逃离迷宫。现在需要你帮助小青蛙计算出能否用仅剩的体力值跳出迷宫(即达到(0,m-1)位置)。

输入描述:

输入包括n+1行:
 第一行为三个整数n,m(3 <= m,n <= 10),P(1 <= P <= 100)
 接下来的n行:
 每行m个0或者1,以空格分隔

输出描述:

如果能逃离迷宫,则输出一行体力消耗最小的路径,输出格式见样例所示;如果不能逃离迷宫,则输出"Can not escape!"。 测试数据保证答案唯一

示例1

输入

4 4 10 1 0 0 1 1 1 0 1 0 1 1 1 0 0 1 1

输出

[0,0],[1,0],[1,1],[2,1],[2,2],[2,3],[1,3],[0,3]

算法知识视频讲解

Python

许愿offer！！！！！

data = [int(i) for i in input().strip().split(' ')]
n,m,p = data[0],data[1],data[2]
res= []
for i in range(n):
    res.append([int(i) for i in input().strip().split(' ')])
#print(res)
lujing = []
def helper(i,j,p,lujing):
    if p < 0:
        return False
    if i < 0&nbs***bsp;j >= m&nbs***bsp;i >= n&nbs***bsp;j < 0:
        return False
    if res[i][j] == 0:
        return False
    if p <= 0 and (i != 0 and j!= m-1):
        return False
    lujing += [[i,j]]
    if i == 0 and j == m-1 and p >=0:
        return True
    res[i][j] = 0
    result = helper(i,j+1,p-1,lujing)&nbs***bsp;helper(i-1,j,p-3,lujing)&nbs***bsp;helper(i+1,j,p,lujing)&nbs***bsp;  helper(i,j-1,p-1,lujing) 
    
    res[i][j] = 1
    return result
if helper(0,0,p,lujing) == True:
    res_str= ''
    for i,r in enumerate(lujing):
        res_str += '['+str(r[0])+','+str(r[1])+']'+','
    print(res_str[:-1])
else:
    print('Can not escape!')

发表于 2020-07-23 22:32:43 回复(0)

Python

冉龙宇

简单的深度优先遍历，只是有点费时间。

nmp = list(map(int, input().strip().split()))
n = nmp[0]
m = nmp[1]
p = nmp[2]
nmli = []
for i in range(n):
    nmli.append(list(map(int, input().strip().split())))
def dfs(nmli, route, p):  # 地图，路径，剩余体力
    x = route[-1][0]  # 当前位置
    y = route[-1][1]
    if p >= 0 and x == 0 and y == len(nmli[0]) - 1:  # 如果到终点了
        return route
    if p <= 0:  # 如果体力值小于等于0
        return False
    result = [0] * (len(nmli) * len(nmli[0]) + 1)
    if x - 1 >= 0 and nmli[x - 1][y] != 0:  # 可以往上走
        if [x - 1, y] not in route:  # 上没有走过
            re = dfs(nmli, route + [[x - 1, y]], p - 3)
            if re != False and len(re) < len(result):
                result = re
    if x + 1 < len(nmli) and nmli[x + 1][y] != 0:  # 可以往下走
        if [x + 1, y] not in route:  # 下没有走过
            re = dfs(nmli, route + [[x + 1, y]], p)
            if re != False and len(re) < len(result):
                result = re
    if y + 1 < len(nmli[0]) and nmli[x][y + 1] != 0:  # 可以往右走
        if [x, y + 1] not in route:  # 右没有走过
            re = dfs(nmli, route + [[x, y + 1]], p - 1)
            if re != False and len(re) < len(result):
                result = re
    if y - 1 >= 0 and nmli[x][y - 1] != 0:  # 可以往左走
        if [x, y - 1] not in route:  # 左没有走过
            re = dfs(nmli, route + [[x, y - 1]], p - 1)
            if re != False and len(re) < len(result):
                result = re
    if len(result) != len(nmli) * len(nmli[0]) + 1:
        return result
    else:
        return False
result = dfs(nmli, [[0, 0]], p)
if result != False:
    sout = ""
    for line in result:
        sout += '['
        sout += str(line[0])
        sout += ','
        sout += str(line[1])
        sout += ']'
        sout += ','
    print(sout[:-1])
else:
    print("Can not escape!")
'''
4 4 10
1 0 0 1
1 1 0 1
0 1 1 1
0 0 1 1
'''

发表于 2019-08-26 17:01:22 回复(0)

Python

neekity

###############BFS#############
n,m,p=map(int,input().split())
board=[]
for _ in range(n):
    tmp=list(map(int,input().split()))
    board.append(tmp)
dirc=[(1,0,0),(0,1,1),(0,-1,1),(-1,0,3)]
flag=True
q=[(0,0,p)]
visit=[[(-1,-1,-1)for _ in range(m)]for _ in range(n)]
visit[0][0]=(0,0,p)
while q and flag:
    cur=q.pop(0)
    x,y,remain=cur[0],cur[1],cur[2]
    for i in range(4):
        dx,dy,consume=dirc[i][0],dirc[i][1],dirc[i][2]
        nx,ny=dx+x,dy+y
        if 0<=nx<n and 0<=ny<m and remain-consume>visit[nx][ny][2] and board[nx][ny]==1:
            if nx==0 and ny ==m-1:
                flag=False
                visit[0][m-1]=(x,y,remain-consume)
                break
            q.append((nx,ny,remain-consume))
            visit[nx][ny]=(x,y,remain-consume)
if visit[0][m-1][2]==-1: print("Can not escape!")
else:
    res=[[0,m-1]]
    while res[0]!=[0,0]:
        prex,prey=res[0][0],res[0][1]
        x,y=visit[prex][prey][0],visit[prex][prey][1]
        res=[[x,y]]+res
    a=str(res)
    a=a.replace(' ','')
    
    print(a[1:-1])
'''
###############DFS+剪枝#############
res=[-1,'$']
visit=[[-1]*m for _ in range(n)]
def dfs(x,y,remain,tmp):
    visit[x][y]=remain
    if x==0 and y ==m-1:
        if res[0]<remain:
            res[0]=remain
            res[1]=tmp+'['+str(x)+','+str(y)+']'
        return 
    for i in range(4):
        dx,dy,consume=dirc[i][0],dirc[i][1],dirc[i][2]
        nx,ny=dx+x,dy+y
        if 0<=nx<n and 0<=ny<m and remain-consume>visit[nx][ny] and board[nx][ny]==1:
            dfs(nx,ny,remain-consume,tmp+'['+str(x)+','+str(y)+']'+',')
dfs(0,0,p,'')
if res[0]==-1: print("Can not escape!")
else:
    print(res[1])
'''

发表于 2019-03-17 13:47:49 回复(0)

Python

奋起的小孩



'''引用@rober 大佬的框架改写如下'''
n,m,p = [int(x) for x in input().split()]
def dfs(grid,visited,path,i,j,p):
    path.append([i,j])
    if i == 0 and j == m - 1:
        return 
    visited[i][j] = True
    if i-1>=0 and grid[i-1][j] and visited[i-1][j]==0 and p>=0: 
        dfs(grid,visited,path,i-1,j,p)
    if j-1>=0 and grid[i][j-1] and visited[i][j-1]==0 and p-1>=0: 
        dfs(grid,visited,path,i,j-1,p-1)
    if j+1=0: 
        dfs(grid,visited,path,i,j+1,p-1)
    if i+1=0:  
        dfs(grid,visited,path,i+1,j,p-3)
    if path[-1][0]==0 and path[-1][1]==m-1:
        return
    path.pop()
grid = []
for i in range(n):
    grid.append([int(x) for x in input().split()])
visited = [[False for i in range(m)] for i in range(n)]
path = []
dfs(grid,visited,path,0,0,p)
if path and path[-1][0]==0 and path[-1][1]==m-1:
    res = ''
    for i in path:
        res += '['+str(i[0])+','+str(i[1])+']'+',' 
    print(res[:-1])
else:
    print('Can not escape!')

编辑于 2018-08-19 19:29:22 回复(0)

Python

Zoom内推助手

（1）优先级：右-上-下-左
（2）不能回到来时的路(while)

n, m, p = map(int, input().split())
obstacles = []
res = ['[0,0]']
for _ in range(n):
    obstacles.append(list(map(int, input().split())))
cur_r, cur_c = 0, 0

while p > 0:
    if cur_r == 0 and cur_c == m - 1:
        break
    move = False
    #right
    while p > 0 and cur_c < m - 1 and obstacles[cur_r][cur_c+1] == 1:
        cur_c += 1
        p -= 1
        res.append('[%d,%d]'%(cur_r,cur_c))
        move = True
    if move:
        continue
    #up
    while p > 0 and cur_r > 0 and obstacles[cur_r-1][cur_c] == 1:
        cur_r -= 1
        p -= 3
        res.append('[%d,%d]'%(cur_r,cur_c))
        move = True
    if move:
        continue
    #down
    while p > 0 and cur_r < n - 1 and obstacles[cur_r+1][cur_c] == 1:
        if obstacles[cur_r][cur_c+1] == 1:
            break
        cur_r += 1
        res.append('[%d,%d]'%(cur_r,cur_c))
        move = True
    if move:
        continue
    #left
    while p > 0 and cur_c > 0 and obstacles[cur_r][cur_c-1] == 1:
        cur_c -= 1
        p -= 1
        res.append('[%d,%d]'%(cur_r,cur_c))
        move = True
    if move:
        continue

if p >= 0 and (cur_r == 0 and cur_c == m - 1):
    print(','.join(res))
else:
    print("Can not escape!")

发表于 2018-08-01 19:27:12 回复(0)

Python

吴上天命

# -*- coding: utf8 -*-

def isValid(matrix,n,m,p,x,y,visited):
    isvisit=(x*m+y in visited) #是否访问
    isvalid=(0<=x<n and 0<=y<m) and matrix[x][y]==1#是否通路
    hasp=(p>=0)#是否有剩余能量值
    return not isvisit and isvalid and hasp #是否可走

def getPath(matrix, n, m, p, x, y, visited, path):
    if (x, y) == (0, m - 1):
        return True
    else:
        nextpos=[(x,y+1,p-1),(x-1,y,p-3),(x,y-1,p-1),(x+1,y,p)]
        #向右，向上，向左，向下 (贪心思想，尽可能以最小的消耗靠近终点--右上角
        for nextx,nexty,nextp in nextpos:
            if isValid(matrix,n,m,nextp,nextx,nexty,visited):
                path.append([nextx,nexty])
                visited.add(nextx * m + nexty)
                if getPath(matrix, n, m, nextp,nextx,nexty, visited, path):
                    return True
                path.pop(-1)
                visited.remove(nextx * m + nexty)
        return False

if __name__ == "__main__":
    n, m, p = map(int, raw_input().split(' '))
    matrix = []
    for i in range(n):
        matrix.append(map(int, raw_input().split(' ')))
    visited = set()
    path = [[0, 0]]
    if getPath(matrix, n, m, p, 0, 0, visited, path):
        print ','.join(map(str, path)).replace(' ', '')
    else:
        print "Can not escape!"

编辑于 2018-07-16 12:13:53 回复(1)

Python

离疏

n,m,P=list(map(int,input().split()))
migong=[list(map(int,input().split())) for i in range(n)]
x0,y0=0,0
power_matrix = [[None for j in range(m)] for i in range(n)]# 体力矩阵，记录到达该点剩余的体力。初始是-1。
power_matrix[x0][y0] = [0,0,P]#保存到达[x, y]的前一个点和到达[x, y]剩余的p
current_points=[[x0,y0]] # 第一轮所在的探索点（多个）
flag=True
while current_points and flag:
    x,y=current_points.pop(0)
    for step in [[-1,0],[1,0],[0,-1],[0,1]]:
        x_,y_=x+step[0],y+step[1]
        if x_ < 0 or x_ >= n or y_ < 0 or y_ >= m:  # 检查是否越界
            continue
        if migong[x_][y_] ==0 or power_matrix[x_][y_] is not None:  # 检查该点是否可以通行，或者已经达到过
            continue
        else:
            if step==[-1,0]:#向上爬消耗3体力
                newP=power_matrix[x][y][2]-3
            elif step==[1,0]:#向下爬不消耗体力
                newP=power_matrix[x][y][2]
            else:#水平移动消耗1体力
                newP=power_matrix[x][y][2]-1
            power_matrix[x_][y_]=[x,y,newP]
            current_points.append([x_, y_])  # 该点添加到下一轮探索点里。
            if [x_,y_]==[0,m-1]:#遍历到0，m-1点就可以停止了
                flag=False
                break
if power_matrix[0][m-1][2]<0:
    print('Can not escape!')
else:
    res=[]
    x,y=0,m-1
    while [x,y]!=[0,0]:
        res.append([x,y])
        [x,y]=power_matrix[x][y][0],power_matrix[x][y][1]
    res.append([0,0])
    print(','.join(['[{},{}]'.format(x[0],x[1]) for x in res[::-1]]))

发表于 2018-07-04 11:16:01 回复(0)

Python

新鲜菜鸡🐔

暴力搜索！

这道题感觉因为每一步体力根据方向损失固定，所以到某个点，使用步数最少一定损失体力最少，多的步都是浪费体力，所以可以从起点开始广搜，一直最先搜到终点的路径是最剩体力的，如果体力还小于0，就不能到。

n, m, p = [int(x) for x in input().split()]
mat0 = []
for _ in range(n):
    mat0.append([int(x) for x in input().split()])
mat1 = [[None for j in range(m)] for i in range(n)]
mat1[0][0] = [0, 0, p]  # mat1保存到达[x, y]的前一个点和到达[x, y]剩余的p
route = [[0, 0]]
steps = [[1, 0], [-1, 0], [0, 1], [0, -1]]
flag = True     #其实遍历到0，m-1点就可以停止了
while route and flag:
    x0, y0 = route.pop(0)
    for step in steps:
        x1, y1 = x0 + step[0], y0 + step[1]
        if 0 <= x1 < n and 0 <= y1 < m and mat0[x1][y1] and mat1[x1][y1] is None:
            if step[0] == -1:
                new_p = mat1[x0][y0][2] - 3
            elif step[0] == 0:
                new_p = mat1[x0][y0][2] - 1
            else:
                new_p = mat1[x0][y0][2]
            mat1[x1][y1] = [x0, y0, new_p]
            route.append([x1, y1])
            if x1==0 and y1==m-1:
                flag = False
                break
if mat1[0][m-1][2] < 0:
    print('Can not escape!')
else:
    res = []
    x, y = 0, m-1
    while [x, y] != [0, 0]:
        res.append([x, y])
        x, y = mat1[x][y][0], mat1[x][y][1]
    res.append([0, 0])
    print(','.join(['[{},{}]'.format(x[0], x[1]) for x in res[::-1]]))

编辑于 2018-05-23 18:57:24 回复(1)

Python

小欣8

if __name__ == '__main__':
    n, m, p = [int(x) for x in input().split()]
    mat0 = []
    for _ in range(n):
        mat0.append([int(x) for x in input().split()])
    mat1 = [[None for j in range(m)] for i in range(n)]
    mat1[0][0] = [0, 0, p]  # mat1保存到达[x, y]的前一个点和到达[x, y]剩余的p
    route = [[0, 0]]
    steps = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    while route:
        x0, y0 = route.pop(0)
        for step in steps:
            x1, y1 = x0 + step[0], y0 + step[1]
            if 0 <= x1 < n and 0 <= y1 < m and mat0[x1][y1] and mat1[x1][y1] is None:
                if step[0] == -1:
                    new_p = mat1[x0][y0][2] - 3
                elif step[0] == 0:
                    new_p = mat1[x0][y0][2] - 1
                else:
                    new_p = mat1[x0][y0][2]
                mat1[x1][y1] = [x0, y0, new_p]
                route.append([x1, y1])
    print(mat1)
    if mat1[0][m-1][2] < 0:
        print('Can not escape!')
    else:
        res = []
        x, y = 0, m-1
        while [x, y] != [0, 0]:
            res.append([x, y])
            x, y = mat1[x][y][0], mat1[x][y][1]
        res.append([0, 0])
        print(','.join(['[{},{}]'.format(x[0], x[1]) for x in res[::-1]]))

发表于 2017-10-01 09:47:00 回复(0)

Python

Benjaminz

BFS直到找出路径或者体力用完

#coding=utf-8

import sys
m,n,p=map(int,raw_input().split())
a=[] for i in range(m):
   a.append(map(int,raw_input().split()))
v=[[0 for i in range(n)]for j in range(m)]#visit d=[[0,1],[-1,0],[0,-1],[1,0]]#direction c=[1,3,1,0]#cost q=[]
s=[]#step s.append([0,0])#begin at (0,0) v[0][0]=1#(0,0)has been visited i,j=s[-1]#init position k=0 flag=False while k<4:#BFS  x=i+d[k][0]
   y=j+d[k][1] if x>=0 and y>=0 and x<m and y<n and a[x][y]==1 and v[x][y]==0:
      s.append([x,y])
      v[x][y]=1  q.append(c[k])
      p-=q[-1]
      i=x
      j=y
      k=-1  if p<0:
      flag=True  break  if x==0 and y==n-1: break  if k==3:
      s.pop()
      p+=q[-1]
      q.pop()
      i=s[-1][0]
      j=s[-1][1]
      k=-1  k+=1 if flag: print 'Can not escape!' else: for k in range(len(s)-1): print '[%d,%d],'%(s[k][0],s[k][1]),
      sys.stdout.softspace=0  print '[%d,%d]'%(s[len(s)-1][0],s[len(s)-1][1])